Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Adding items to end of linked list

I'm studying for an exam, and this is a problem from an old test:

We have a singly linked list with a list head with the following declaration:

class Node {
    Object data;
    Node next;
    Node(Object d,Node n) {
        data = d;
        next = n;
    }
}

Write a method void addLast(Node header, Object x) that adds x at the end of the list.

I know that if I actually had something like:

LinkedList someList = new LinkedList();

I could just add items to the end by doing:

list.addLast(x);

But how can I do it here?

like image 607
John Avatar asked Mar 08 '11 18:03

John


3 Answers

class Node {
    Object data;
    Node next;
    Node(Object d,Node n) {
        data = d ;
        next = n ;
       }

   public static Node addLast(Node header, Object x) {
       // save the reference to the header so we can return it.
       Node ret = header;

       // check base case, header is null.
       if (header == null) {
           return new Node(x, null);
       }

       // loop until we find the end of the list
       while ((header.next != null)) {
           header = header.next;
       }

       // set the new node to the Object x, next will be null.
       header.next = new Node(x, null);
       return ret;
   }
}
like image 106
therin Avatar answered Oct 18 '22 23:10

therin


You want to navigate through the entire linked list using a loop and checking the "next" value for each node. The last node will be the one whose next value is null. Simply make this node's next value a new node which you create with the input data.

node temp = first; // starts with the first node.

    while (temp.next != null)
    {
       temp = temp.next;
    }

temp.next = new Node(header, x);

That's the basic idea. This is of course, pseudo code, but it should be simple enough to implement.

like image 8
Benjamin S Avatar answered Oct 18 '22 23:10

Benjamin S


public static Node insertNodeAtTail(Node head,Object data) {
               Node node = new Node(data);
                 node.next = null;
                if (head == null){
                    return node;
                }
                else{
                    Node temp = head;
                    while(temp.next != null){
                        temp = temp.next;
                    }
                    temp.next = node; 
                    return head;
                }        
    }
like image 4
Ashutosh Mishra Avatar answered Oct 19 '22 00:10

Ashutosh Mishra