Linked List – Computer Science

Do My Computer Homework!

1)      Assume you are working with a doubly linked list, based on the following node:

class node {

float data;

node next;

nodeprev;

}

Write an insert module – which takes a “head” pointer as a parameter (along with the data to be inserted), and inserts to the head of the list.  Consider the empty list case.

 

public void insert(float float_var){

            Node last = post.prev;

            Node x = new Node();

            x.data = float_var;

            x.next = last;

            x.prev = post;

            post.next = x;

            last.prev = x;

}

 

2)      Given the declarations below, write a recursive isThere module for a linked list implementation of the “Node” class.  The method will take 2 values – a “reference” to the node being looked at called “pointer”, and a search value called “lookingfor”.  Assume the existence of a boolen isEmpty method.  Also assume the list is “capped off” with Null.

class node {

int data;

node next;

}

                        public Boolean isThere(node reference, int value){

                                    node test = reference;

                                    if(!isEmpty(test)){

                                                if(test.data == value)

                                                            return true;

                                                else

                                                            isThere(test.next, value);

                                    }

                                    else

                                                return false;

}

3)      I have a stack implemented with an array (20 cells) of string objects. There is an integer variable called Top which holds the index of first open cell on the stack (the top) (example shown below).Write out the pseudocode for a “pop” method.  Create an “is_empty” method which returns a Boolean value (true for empty, false for not empty), then call it from your pop method.

 

[3]

[2]

3

[1]

Stack                 [0]                  Top

Is_empty method :

public Boolean is_Empty(int[] arrayStack, index_level){

            if (arrayStack[index_level] != NULL)                 

//Check if the Stack at index level is empty

                        return false;

            return true;

}

 

Pseudocode for pop method :

Function pop is

if Top is greater than zero

            set arrayStack at index Top := NULL

            Subtract one from Top 

 

4)      I have a queue implemented with a linked list.  There are two variables (front and rear).  Write the pseducode for a “count” method.  This method will return the number of items in the queue.  Assume that this data is not stored anywhere else.

 

Pseudocode for count method :

 

Function count(node) is     // takes any node within the queue

            Queue_length := 1

                                                Set frontpointer := pointer to front

            set rearpointer := pointer to rear

                                        //Split the nodes and start counting

            while frontpointer is not NULL               // Front Counting

                        Queue_length++

                        Set frontpointer := pointer to front

            while rearpointer is not NULL                 // Rear Counting

                        Queue_length++

                        Set rearpointer := pointer to rear

            Return Queue_length;

 

5)      Write the pseducode for a method that adds new items to the “end” of a linked list (list nodes hold a character as data).  The list only has a “head” pointer, so your method needs to make its way through the list to add the new element.  Assume the list is capped off with NULL.  Watch for the empty case.

 

Pseducode:

Function add_end(list, pointer to head, value) is

            While pointer to head is not NULL           // traverse till the end of the list

                        Set Pointer to head := list.next

            Initialize node new_node := new node  // create a new node

            Set list.next := pointer to new_node        // assign next pointer to the                                                                                               new_node

            Set new_node.data:= value                       // assign values to the new node

            Set new_node.next:= NULL                      // next points to null because it                                                                                        is at the tail of the list