Adding items to end of linked list

Question

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

User · Answer

Here s a hint  you have a graph of nodes in the linked list  and you always keep a reference to head which is the first node in the linkedList  next points to the next node in the linkedlist  so when next is null you are at the end of the list

User · Answer

loop to the last element of the linked list which have next pointer to null then modify the next pointer to point to a new node which has the data object and next pointer   null

User · Answer

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

User · Answer

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

User · Answer

Here is a partial solution to your linked list class  I have left the rest of the implementation to you  and also left the good suggestion to add a tail node as part of the linked list to you as well   The node file    public class Node        private Object data       private Node next        public Node Object d                  data   d           next   null             public Object GetItem                 return data             public Node GetNext                 return next             public void SetNext Node toAppend                next   toAppend            And here is a Linked List file    public class LL       private Node head       public LL                 head   null             public void AddToEnd String x                Node current   head              as you mentioned  this is the base case         if current    null                head   new Node x               head SetNext null                         you should understand this part thoroughly              this is the code that traverses the list             the germane thing to see is that when the             link to the next node is null  we are at the             end of the list          else               while current GetNext      null                  current   current GetNext                    add new node at the end         Node toAppend   new Node x               current SetNext toAppend

User · Answer

The above programs might give you NullPointerException  This is an easier way to add an element to the end of linkedList   public class LinkedList       Node head       public static class Node          int data          Node next           Node int item               data   item              next   null                      public static void main String args             LinkedList ll   new LinkedList            ll head   new Node 1           Node second   new Node 2           Node third   new Node 3           Node fourth   new Node 4            ll head next   second          second next   third          third next   fourth          fourth next   null           ll printList            System out println  Add element 100 to the last            ll addLast 100           ll printList              public void printList            Node t   head          while n    null               System out println t data               t   t next                        public void addLast int item           Node new item   new Node item           if head    null               head   new item              return                    new item next   null           Node last   head          Node temp   null          while last    null               if last    null                  temp   last              last   last next                        temp next   new item             return

User · Answer

If you keep track of the tail node  you don t need to loop through every element in the list  Just update the tail to point to the new node  AddValueToListEnd value        var node   new Node value        if  this head            this head   node          this tail   node        else           this tail next   node    point old tail to new node                    this tail   node    now set the new node as the new tail    In plain English   Create a new node with the given value If the list is empty  point head and tail to the new node If the list is not empty  set the old tail next to be the new node In either case  update the tail pointer to be the new node

User · Answer

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

User · Answer

The addLast   needs some optimisation as the while loop inside addLast   has O n  complexity  Below is my implementation of LinkedList  Run the code with ll addLastx i  once and run it with ll addLast i  again   you can see their is a lot of difference in processing time of addLastx   with addLast       Node java  package in datastructure java LinkedList         Created by abhishek panda on 07 07 17     public final class Node       int data      Node next       Node  int data          this data   data            public String toString          return this data  --   this next            LinkedList java  package in datastructure java LinkedList  import java util ArrayList  import java util Date   public class LinkedList        Node head      Node lastx                  description To append node at end looping all nodes from head         param data             public void addLast int data            if head    null               head   new Node data               return                    Node last   head          while last next    null                last   last next                    last next   new Node data                           description This keep track on last node and append to it         param data             public void addLastx int data            if head    null               head   new Node data               lastx   head              return                    if lastx next    null               lastx next   new Node data               lastx   lastx next                        public String toString            ArrayList lt Integer gt  arrayList   new ArrayList lt Integer gt  10           Node current   head          while current next    null                arrayList add current data               current   current next                    if current next    null                arrayList add current data                     return arrayList toString                public static void main String   args            LinkedList ll   new LinkedList                            description Checking the code optimization of append code                     Date startTime   new Date            for  int i   0   i  lt  100000   i                 ll addLastx i                     Date endTime   new Date            System out println  To total processing time        endTime getTime  -startTime getTime              System out println ll toString

[java] Adding items to end of linked list

Examples related to java

Examples related to linked-list