Creating a LinkedList class from scratch

Question

We were given an assignment to create a LinkedList from scratch  and there are absolutely no readings given to guide us on this migrane-causing task  Also everything online seems to just use Java s built in LinkedList methods and stuff  Anyway  linked lists make perfect sense when using Java s default stuff  but creating it from scratch makes no sense whatsoever  Lets say I have  public class LinkedList     private LinkedList next      private final String word       constructor   public LinkedList String word  LinkedList next        this word   word      this next   next        And thus magically we have a linked list  What is going on  How have I created a linked list like this  How does this work  I m supposed to write an append method that adds a the given String word parameter to the end of this linkedlist  I tried looking at the addLast built in method for built in java linkedlist class  but it s no help to me  as I really dont understand whats going on  Anyone care to help me out

User · Answer

Hint 1  read the description of linked lists at http   en wikipedia org wiki Linked list  Hint 2  the Java implementation of LinkedList is a doubly linked list   Yours is a singly linked list   The algorithms don t directly apply     Also          but creating  a linked list class  from scratch makes no sense whatsoever     It depends on what the required outcome of the work is   If the goal is to produce code that meets certain functional   non-functional requirements  then you are right   If the real goal is for you to learn how to program   design APIs   implement non-trivial data structures  then the utility of the final product is almost entirely irrelevant      And thus magically we have a linked list   What you actually have there is a open data type  that could be used to build a  sort of  list   But that is not what your teacher wants   And it certainly would not be considered to be a useful list abstraction   A useful abstraction would include    methods to do the things that programmers don t want to have to repeat over and over again  and an abstraction layer that stops programmers  breaking  the list  e g  by accidentally creating a cycle  or accidentally stitching a sublist in two lists to create an inverted tree

User · Answer

If you re actually building a real system  then yes  you d typically just use the stuff in the standard library if what you need is available there  That said  don t think of this as a pointless exercise  It s good to understand how things work  and understanding linked lists is an important step towards understanding more complex data structures  many of which don t exist in the standard libraries   There are some differences between the way you re creating a linked list and the way the Java collections API does it  The Collections API is trying to adhere to a more complicated interface  The Collections API linked list is also a doubly linked list  while you re building a singly linked list  What you re doing is more appropriate for a class assignment    With your LinkedList class  an instance will always be a list of at least one element  With this kind of setup you d use null for when you need an empty list   Think of next as being  the rest of the list   In fact  many similar implementations use the name  tail  instead of  next     Here s a diagram of a LinkedList containing 3 elements     Note that it s a LinkedList object pointing to a word   Hello   and a list of 2 elements  The list of 2 elements has a word   Stack   and a list of 1 element  That list of 1 element has a word   Overflow   and an empty list  null   So you can treat next as just another list that happens to be one element shorter   You may want to add another constructor that just takes a String  and sets next to null  This would be for creating a 1-element list   To append  you check if next is null  If it is  create a new one element list and set next to that   next   new LinkedList word     If next isn t null  then append to next instead   next append word     This is the recursive approach  which is the least amount of code  You can turn that into an iterative solution which would be more efficient in Java   and wouldn t risk a stack overflow with very long lists  but I m guessing that level of complexity isn t needed for your assignment       Some languages have tail call elimination  which is an optimization that lets the language implementation convert  tail calls   a call to another function as the very last step before returning  into  effectively  a  goto   This makes such code completely avoid using the stack  which makes it safer  you can t overflow the stack if you don t use the stack  and typically more efficient  Scheme is probably the most well known example of a language with this feature

User · Answer

Pleas find bellow Program    class Node       int data      Node next       public Node int data            this data   data          this next   null           public class LinkedListManual        Node node       public void pushElement int next node            Node nd   new Node next node           nd next   node          node   nd             public int getSize             Node temp   node          int count   0          while  temp    null                count                temp   temp next                    return count             public void getElement             Node temp   node          while  temp    null                System out println temp data               temp   temp next                       public static void main String   args            LinkedListManual obj   new LinkedListManual            obj pushElement 1           obj pushElement 2           obj pushElement 3           obj getElement      get element         System out println obj getSize        get size of link list

User · Answer

Linked List Program  with following functionalities  1 Insert At Start 2 Insert At End 3 Insert At any Position 4 Delete At any Position 5 Display  6 Get Size 7 Empty Status 8 Replace data at given postion 9 Search Element by position 10 Delete a Node by Given Data 11 Search Element Iteratively 12 Search Element Recursively      package com elegant ds linkedlist practice   import java util Scanner   class Node        Node link   null      int data   0       public Node             link   null          data   0             public Node int data  Node link            this data   data          this link   null             public Node getLink             return link             public void setLink Node link            this link   link             public int getData             return data             public void setData int data            this data   data            class SinglyLinkedListImpl        Node start   null      Node end   null      int size   0       public SinglyLinkedListImpl             start   null          end   null          size   0             public void insertAtStart int data            Node nptr   new Node data  null           if  start    null                start   nptr              end   start            else               nptr setLink start               start   nptr                    size               public void insertAtEnd int data            Node nptr   new Node data  null           if  start    null                start   nptr              end   nptr            else               end setLink nptr               end   nptr                    size               public void insertAtPosition int position  int data            Node nptr   new Node data  null           Node ptr   start          position   position - 1          for  int i   1  i  lt  size  i                  if  i    position                    Node temp   ptr getLink                    ptr setLink nptr                   nptr setLink temp                   break                            ptr   ptr getLink                      size               public void repleaceDataAtPosition int position  int data            if  start    null                System out println  Empty                 return                     Node ptr   start          for  int i   1  i  lt  size  i                  if  i    position                    ptr setData data                             ptr   ptr getLink                         public void deleteAtPosition int position            if  start    null                System out println  Empty                 return                     if  position    size                Node startPtr   start              Node endPtr   start              while  startPtr    null                    endPtr   startPtr                  startPtr   startPtr getLink                              end   endPtr              end setLink null               size--              return                     Node ptr   start          position   position - 1          for  int i   1  i  lt  size  i                   if  i    position                    Node temp   ptr getLink                    temp   temp getLink                    ptr setLink temp                   break                            ptr   ptr getLink                      size--             public void deleteNodeByGivenData int data            if  start    null                System out println  Empty                 return                     if  start getData      data  amp  amp  start getLink      null                start   null              end   null              size--              return                     if  start getData      data  amp  amp  start getLink      null                start   start getLink                size--              return                     if  end getData      data                Node startPtr   start              Node endPtr   start               startPtr   startPtr getLink                while  startPtr getLink      null                    endPtr   startPtr                  startPtr   startPtr getLink                              end   endPtr              end setLink null               size--              return                     Node startPtr   start          Node prevLink   startPtr          startPtr   startPtr getLink            while  startPtr getData      data  amp  amp  startPtr getLink      null                prevLink   startPtr              startPtr   startPtr getLink                      if  startPtr getData      data                Node temp   prevLink getLink                temp   temp getLink                prevLink setLink temp               size--              return                     System out println data     not found                public void disply             if  start    null                System out println  Empty                 return                     if  start getLink      null                System out println start getData                 return                     Node ptr   start          System out print ptr getData      - gt             ptr   start getLink            while  ptr getLink      null                System out print ptr getData      - gt                 ptr   ptr getLink                      System out println ptr getData       n               public void searchElementByPosition int position            if  position    1                System out println  Element at     position     is       start getData                 return                     if  position    size                System out println  Element at     position     is       end getData                 return                     Node ptr   start          for  int i   1  i  lt  size  i                  if  i    position                    System out println  Element at     position     is       ptr getData                     break                            ptr   ptr getLink                         public void searchElementIteratively int data             if  isEmpty                  System out println  Empty                 return                     if  start getData      data                System out println data     found at     1     position                return                     if  start getLink      null  amp  amp  end getData      data                System out println data     found at     size     position                return                     Node startPtr   start          int position   0          while  startPtr getLink      null                  position              if  startPtr getData      data                    break                            startPtr   startPtr getLink                      if  startPtr getData      data                System out println data     found at     position               return                     System out println data     No found                public void searchElementRecursively Node start  int data  int count             if  isEmpty                  System out println  Empty                 return                    if  start getData      data                System out println data     found at        count                return                    if  start getLink      null                System out println data     not found                 return                    searchElementRecursively start getLink    data    count              public int getSize             return size             public boolean isEmpty             return start    null           public class SinglyLinkedList         SuppressWarnings  resource       public static void main String   args            SinglyLinkedListImpl listImpl   new SinglyLinkedListImpl            System out println  Singly Linked list               boolean yes   true          do               System out println  1 Insert At Start                  System out println  2 Insert At End                  System out println  3 Insert At any Position                  System out println  4 Delete At any Position                  System out println  5 Display                  System out println  6 Get Size                System out println  7 Empty Status                System out println  8 Replace data at given postion                System out println  9 Search Element by position                 System out println  10 Delete a Node by Given Data                System out println  11 Search Element Iteratively                System out println  12 Search Element Recursively                System out println  13 Exit                  Scanner scanner   new Scanner System in               int choice   scanner nextInt                switch  choice                case 1                  listImpl insertAtStart scanner nextInt                     break               case 2                  listImpl insertAtEnd scanner nextInt                     break               case 3                  int position   scanner nextInt                    if  position  lt   1    position  gt  listImpl getSize                          System out println  invalid position                       else                       listImpl insertAtPosition position  scanner nextInt                                       break               case 4                  int deletePosition   scanner nextInt                    if  deletePosition  lt   1    deletePosition  gt  listImpl getSize                          System out println  invalid position                       else                       listImpl deleteAtPosition deletePosition                                     break               case 5                  listImpl disply                    break               case 6                  System out println listImpl getSize                     break               case 7                  System out println listImpl isEmpty                     break               case 8                  int replacePosition   scanner nextInt                    if  replacePosition  lt  1    replacePosition  gt  listImpl getSize                          System out println  Invalid position                       else                       listImpl repleaceDataAtPosition replacePosition  scanner nextInt                                       break               case 9                  int searchPosition   scanner nextInt                    if  searchPosition  lt  1    searchPosition  gt  listImpl getSize                          System out println  Invalid position                       else                       listImpl searchElementByPosition searchPosition                                     break               case 10                  listImpl deleteNodeByGivenData scanner nextInt                     break               case 11                  listImpl searchElementIteratively scanner nextInt                     break               case 12                  listImpl searchElementRecursively listImpl start  scanner nextInt    0                   break               default                  System out println  invalid choice                    break                          while  yes             It will help you in linked list

User · Answer

How have I created a linkedlist like this  How does this work  This is all a linked list is   An item with a link to the next item in the list   As long as you keep a reference to the item at the beginning of the list  you can traverse the whole thing using each subsequent reference to the next value   To append  all you need to do is find the end of the list  and make the next item the value you want appended  so if this has non-null next  you would have to call append on the next item until you find the end of the list   this next Append word

User · Answer

How about a fully functional implementation of a non-recursive Linked List   I created this for my Algorithms I class as a stepping stone to gain a better understanding before moving onto writing a doubly-linked queue class for an assignment   Here s the code   import java util Iterator  import java util NoSuchElementException   public class LinkedList lt T gt  implements Iterable lt T gt        private Node first      private Node last      private int N       public LinkedList             first   null          last   null          N   0             public void add T item            if  item    null    throw new NullPointerException  The first argument for addLast   is null               if   isEmpty                  Node prev   last              last   new Node item  null               prev next   last                    else               last   new Node item  null               first   last                    N               public boolean remove T item            if  isEmpty      throw new IllegalStateException  Cannot remove   from and empty list               boolean result   false          Node prev   first          Node curr   first          while  curr next    null    curr    last                if  curr data equals item                        remove the last remaining element                 if  N    1    first   null  last   null                       remove first element                 else if  curr equals first     first   first next                       remove last element                 else if  curr equals last     last   prev  last next   null                       remove element                 else   prev next   curr next                    N--                  result   true                  break                            prev   curr              curr   prev next                    return result             public int size             return N             public boolean isEmpty             return N    0             private class Node           private T data          private Node next           public Node T data  Node next                this data   data              this next   next                       public Iterator lt T gt  iterator     return new LinkedListIterator           private class LinkedListIterator implements Iterator lt T gt            private Node current   first           public T next                 if   hasNext      throw new NoSuchElementException                  T item   current data              current   current next              return item                     public boolean hasNext     return current    null             public void remove     throw new UnsupportedOperationException                  Override public String toString             StringBuilder s   new StringBuilder            for  T item   this              s append item                 return s toString               public static void main String   args            LinkedList lt String gt  list   new LinkedList lt  gt             while  StdIn isEmpty                  String input   StdIn readString                if  input equals  print      StdOut println list toString     continue                if  input charAt 0              list add input substring 1    continue                if  input charAt 0       -      list remove input substring 1    continue                break                      Note  It s a pretty basic implementation of a singly-linked-list  The  T  type is a generic type placeholder  Basically  this linked list should work with any type that inherits from Object  If you use it for primitive types be sure to use the nullable class equivalents  ex  Integer  for the  int  type   The  last  variable isn t really necessary except that it shortens insertions to O 1  time  Removals are slow since they run in O N  time but it allows you to remove the first occurrence of a value in the list   If you want you could also look into implementing    addFirst   - add a new item to the beginning of the LinkedList removeFirst   - remove the first item from the LinkedList  removeLast   - remove the last item from the LinkedList addAll   - add a list array of items to the LinkedList removeAll   - remove a list array of items from the LinkedList contains   - check to see if the LinkedList contains an item  contains   - clear all items in the LinkedList   Honestly  it only takes a few lines of code to make this a doubly-linked list  The main difference between this and a doubly-linked-list is that the Node instances of a doubly-linked list require an additional reference that points to the previous element in the list   The benefit of this over a recursive implementation is that it s faster and you don t have to worry about flooding the stack when you traverse large lists    There are 3 commands to test this in the debugger console     Prefixing a value by a     will add it to the list  Prefixing with a  -  will remove the first occurrence from the list  Typing  print  will print out the list with the values separated by spaces    If you have never seen the internals of how one of these works I suggest you step through the following in the debugger    add   - tacks a new node onto the end or initializes the first last values if the list is empty remove   - walks the list from the start-to-end  If it finds a match it removes that item and connects the broken links between the previous and next links in the chain  Special exceptions are added when there is no previous or next link  toString   - uses the foreach iterator to simply walk the list chain from beginning-to-end    While there are better and more efficient approaches for lists like array-lists  understanding how the application traverses via references pointers is integral to understanding how many higher-level data structures work

User · Answer

What you have coded is not a LinkedList  at least not one that I recognize   For this assignment  you want to create two classes   LinkNode LinkedList   A LinkNode has one member field for the data it contains  and a LinkNode reference to the next LinkNode in the LinkedList   Yes  it s a self referential data structure   A LinkedList just has a special LinkNode reference that refers to the first item in the list     When you add an item in the LinkedList  you traverse all the LinkNode s until you reach the last one   This LinkNode s next should be null   You then construct a new LinkNode here  set it s value  and add it to the LinkedList   public class LinkNode         String data      LinkNode next       public LinkNode String item             data   item             public class LinkedList         LinkNode head       public LinkedList String item             head   new LinkNode item               public void add String item               pseudo code  while next isn t null  walk the list          once you reach the end  create a new LinkNode and add the item to it   Then          set the last LinkNode s next to this new LinkNode

User · Answer

class Node     int data       Node link        public Node                   data 0           link null                  Node ptr start temp       void create  throws  IOException                 int n           BufferedReader br new BufferedReader new InputStreamReader System in             System out println  Enter first data             this data Integer parseInt br readLine              ptr this           start ptr           char ins   y            do                         System out println  Wanna Insert another node                    ins  char br read                 br read                 if ins   y                                   temp new Node                     System out println  Enter next data                     temp data Integer parseInt br readLine                      temp link null                   ptr link temp                   temp null                   ptr ptr link                                 while ins   y               public static void main String args   throws IOException               Node first  new Node           first create

User · Answer

Please read this article  How To Implement a LinkedList Class From Scratch In Java  package com crunchify tutorials           author Crunchify com      public class CrunchifyLinkedListTest        public static void main String   args            CrunchifyLinkedList lList   new CrunchifyLinkedList                add elements to LinkedList         lList add  1            lList add  2            lList add  3            lList add  4            lList add  5                           Please note that primitive values can not be added into LinkedList            directly  They must be converted to their corresponding wrapper            class                       System out println  lList - print linkedlist      lList           System out println  lList size   - print linkedlist size      lList size             System out println  lList get 3  - get 3rd element      lList get 3            System out println  lList remove 2  - remove 2nd element      lList remove 2            System out println  lList get 3  - get 3rd element      lList get 3            System out println  lList size   - print linkedlist size      lList size             System out println  lList - print linkedlist      lList            class CrunchifyLinkedList          reference to the head node      private Node head      private int listCount          LinkedList constructor     public CrunchifyLinkedList                this is an empty list  so the reference to the head node            is set to a new node with no data         head   new Node null           listCount   0             public void add Object data         appends the specified element to the end of this list                Node crunchifyTemp   new Node data           Node crunchifyCurrent   head             starting at the head node  crawl to the end of the list         while  crunchifyCurrent getNext      null                crunchifyCurrent   crunchifyCurrent getNext                         the last node s  next  reference set to our new node         crunchifyCurrent setNext crunchifyTemp           listCount      increment the number of elements variable            public void add Object data  int index         inserts the specified element at the specified position in this list               Node crunchifyTemp   new Node data           Node crunchifyCurrent   head             crawl to the requested index or the last element in the list             whichever comes first         for  int i   1  i  lt  index  amp  amp  crunchifyCurrent getNext      null  i                  crunchifyCurrent   crunchifyCurrent getNext                         set the new node s next-node reference to this node s next-node            reference         crunchifyTemp setNext crunchifyCurrent getNext                now set this node s next-node reference to the new node         crunchifyCurrent setNext crunchifyTemp           listCount      increment the number of elements variable            public Object get int index         returns the element at the specified position in this list                   index must be 1 or higher         if  index  lt   0              return null           Node crunchifyCurrent   head getNext            for  int i   1  i  lt  index  i                  if  crunchifyCurrent getNext      null                  return null               crunchifyCurrent   crunchifyCurrent getNext                      return crunchifyCurrent getData               public boolean remove int index         removes the element at the specified position in this list                   if the index is out of range  exit         if  index  lt  1    index  gt  size                return false           Node crunchifyCurrent   head          for  int i   1  i  lt  index  i                  if  crunchifyCurrent getNext      null                  return false               crunchifyCurrent   crunchifyCurrent getNext                      crunchifyCurrent setNext crunchifyCurrent getNext   getNext             listCount--     decrement the number of elements variable         return true             public int size          returns the number of elements in this list                return listCount             public String toString             Node crunchifyCurrent   head getNext            String output               while  crunchifyCurrent    null                output          crunchifyCurrent getData   toString                      crunchifyCurrent   crunchifyCurrent getNext                      return output             private class Node              reference to the next node in the chain             or null if there isn t one          Node next             data carried by this node             could be of any type you need          Object data              Node constructor         public Node Object dataValue                next   null              data   dataValue                        another Node constructor if we want to            specify the node to point to          public Node Object dataValue  Node nextValue                next   nextValue              data   dataValue                        these methods should be self-explanatory         public Object getData                 return data                     public void setData Object dataValue                data   dataValue                     public Node getNext                 return next                     public void setNext Node nextValue                next   nextValue                      Output  lList - print linkedlist   1  2  3  4  5  lList size   - print linkedlist size  5 lList get 3  - get 3rd element  3 lList remove 2  - remove 2nd element  true lList get 3  - get 3rd element  4 lList size   - print linkedlist size  4 lList - print linkedlist   1  3  4  5

User · Answer

Linked list to demonstrate Insert Front  Delete Front  Insert Rear and Delete Rear operations in Java   import java io DataInputStream  import java io IOException    public class LinkedListTest    public static void main String   args           TODO Auto-generated method stub           Node root   null       DataInputStream reader   new DataInputStream System in               int op   0      while op    6            try               System out println  Enter Option  n1 Insert Front 2 Delete Front 3 Insert Rear 4 Delete Rear 5 Display List 6 Exit                  op   reader nextInt                op   Integer parseInt reader readLine                 switch  op                case 1                  System out println  Enter Value                      int val   Integer parseInt reader readLine                     root   insertNodeFront val root                   display root                   break              case 2                  root removeNodeFront root                   display root                   break              case 3                  System out println  Enter Value                      val   Integer parseInt reader readLine                     root   insertNodeRear val root                   display root                   break              case 4                  root removeNodeRear root                   display root                   break              case 5                  display root                   break              default                  System out println  Invalid Option                    break                          catch  Exception e                   TODO Auto-generated catch block             e printStackTrace                        System out println  Exited           try           reader close          catch  IOException e               TODO Auto-generated catch block         e printStackTrace                    static Node insertNodeFront int value  Node root         Node temp   new Node value       if root  null           return temp     as root or first           else               temp next   root          return temp                          static Node removeNodeFront Node root       if root  null           System out println  List is Empty            return null            if root next  null           return null     remove root itself           else               root root next    make next node as root         return root                          static Node insertNodeRear int value  Node root          Node temp   new Node value       Node cur   root      if root  null           return temp     as root or first           else               while cur next  null                        cur   cur next                    cur next   temp          return root                          static Node removeNodeRear Node root       if root  null           System out println  List is Empty            return null            Node cur   root      Node prev   null      if root next  null           return null     remove root itself           else               while cur next  null                        prev   cur              cur   cur next                    prev next null    remove last node         return root                          static void display Node root       System out println  Current List         if root  null           System out println  List is Empty            return            while  root  null           System out print root val  - gt             root root next            System out println       static class Node      int val      Node next      public Node int value               TODO Auto-generated constructor stub         val   value          next   null

User · Answer

Sure  a Linked List is a bit confusing for programming n00bs  pretty much the temptation is to look at it as Russian Dolls  because that s what it seems like  a LinkedList Object in a LinkedList Object   But that s a touch difficult to visualize  instead look at it like a computer   LinkedList   Data   Next Member  Where it s the last member of the list if next is NULL  So a 5 member LinkedList would be   LinkedList Data1  LinkedList Data2  LinkedList Data3  LinkedList Data4  LinkedList Data5  NULL       But you can think of it as simply   Data1 -  Data2 -  Data3 -  Data4 -  Data5 -  NULL  So  how do we find the end of this   Well  we know that the NULL is the end so   public void append LinkedList myNextNode      LinkedList current   this    Make a variable to store a pointer to this LinkedList   while  current next    NULL      While we re not at the last node of the LinkedList     current   current next    Go further down the rabbit hole        current next   myNextNode    Now we re at the end  so simply replace the NULL with another Linked List    return    and we re done      This is very simple code of course  and it will infinitely loop if you feed it a circularly linked list   But that s the basics

[java] Creating a LinkedList class from scratch

Examples related to java

Examples related to data-structures

Examples related to linked-list

Examples related to append