Page 1 of 2 12 LastLast
Results 1 to 20 of 22
Like Tree7Likes

Thread: Implementing Singly Linked List

  1. #1
    Robben is offline Member
    Join Date
    Feb 2015
    Posts
    67
    Rep Power
    0

    Default Implementing Singly Linked List

    I am trying to implement a singly linked list.

    My singly linked list, where I implemented a class named linkedlist, that I defined (this implementation of linkedlist is not the java class linkedlist, it is my own version of linkedlist):

    Java Code:
    public class SinglyLinkedList<E> implements LinkedList<E> {
    
        public class Node<E> {
    
            public Node<E> next;
            public E element;
    
            public Node(E element) {
                
                this.element = element;
            }
    
            public Node (E element, Node<E> next) {
    
                this.element = element;
                this.next = next;
            }
    
            public E getElement() {
    
                return element;
            }
    
            public Node<E> getNext() {
       	
                return next;
            }
    
            public void setElement(E element) {
            
                this.element = element;
            }
    
            public void setNext(Node<E> next) {
            
                this.next = next;
            }
    
        }
    
        public Node<E> head;
        public Node<E> tail;
        public int total;
    
        public SinglyLinkedList() {
    
            this.head = null;
            this.tail = null;	
            total = 0;
        }
    
        public void add(E element) {
    
            Node<E> singlyAdd = new Node<E>(element);
    
            if (tail == null) {
    
                head = singlyAdd;
                tail = singlyAdd;
            } else {
    
                tail.setNext(singlyAdd);
                tail = singlyAdd;
            }
           
            total++;
        }
    }
    But when I go to my main method to add into my SinglyLinkedList, it doesn't add anything. I am wondering what is wrong with my code?
    Last edited by Robben; 04-17-2015 at 08:19 AM.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,423
    Blog Entries
    7
    Rep Power
    27

    Default Re: Implementing Singly Linked List

    Your code looks sensible (after a first superficial read), but what doesn't it do what it's supposed to do and how did you notice it?

    kind regards,

    Jos
    Build a wall around Donald Trump; I'll pay for it.

  3. #3
    Robben is offline Member
    Join Date
    Feb 2015
    Posts
    67
    Rep Power
    0

    Default Re: Implementing Singly Linked List

    Quote Originally Posted by JosAH View Post
    Your code looks sensible (after a first superficial read), but what doesn't it do what it's supposed to do and how did you notice it?

    kind regards,

    Jos
    I made a static method:

    Java Code:
    public class test {
    
        public static void main(String args[]) {  
    
            SinglyLinkedList<Integer> list = new SinglyLinkedList<>();
    
            list.add(2);
    
            System.out.println(list);  
    
        }     
    }
    And it doesn't add the integer 2 to my list.

  4. #4
    Robben is offline Member
    Join Date
    Feb 2015
    Posts
    67
    Rep Power
    0

    Default Re: Implementing Singly Linked List

    Opps, I think it's because I didn't override the toString method.

  5. #5
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,423
    Blog Entries
    7
    Rep Power
    27

    Default Re: Implementing Singly Linked List

    Quote Originally Posted by Robben View Post
    Opps, I think it's because I didn't override the toString method.
    That's a start; if it still doesn't work as you wanted, sprinkle in a couple of System.out.println( ... ) statements near the places in the code that can be suspicous, so you can see what the code actually does (and doesn't) do ...

    kind regards,

    Jos
    Robben likes this.
    Build a wall around Donald Trump; I'll pay for it.

  6. #6
    Robben is offline Member
    Join Date
    Feb 2015
    Posts
    67
    Rep Power
    0

    Default Re: Implementing Singly Linked List

    I ran into the dreaded nullpointerexception. I fear that exception.

    I can't seem to fix it though. It only happens when I use the method clear(). The nullpointer exception is pointing at removeLast() method under nodeBefore.setNext(null). It also points at the method clear().

    Java Code:
    import java.util.Collection;
        import java.util.*;
        
        public class SinglyLinkedList<E> implements LinkedList<E> {
        
            private class Node<E> {
        
                public Node<E> next;
                public E element;
        
                public Node(E element) {
        
                    this.element = element;
                }
        
                public Node (E element, Node<E> next) {
    
                    this.element = element;
                    this.next = next;
                }
        
                public E getElement() {
    
                    return element;
                }
        
                public Node<E> getNext() {
    
                    return next;
                }
        
                public void setElement(E element) {
    
                    this.element = element;
                }
        
                public void setNext(Node<E> next) {
    
                    this.next = next;
                }
        
                public String toString() {
    
                    return ("[" + element + "] ");
                }
            }
        
            public Node<E> head;
            public Node<E> tail;
            public int total;      
        
            public SinglyLinkedList() {
    
                this.head = null;
                this.tail = null; 
                this.total = 0;
            }
        
            public E get(int index) {
        
                if (index < 0 || index > size()) {
                    return null;
                }
        
                if (index == 0) {
                    return head.getElement();
                }
        
                Node<E> singly = head.getNext();
        
                for (int i = 1; i < index; i ++) {
        
                    if (singly.getNext() == null) {
                      return null;
                    }       
        
                    singly = singly.getNext();      
                }
        
                System.out.println("\n" + singly.getElement());
            
                return singly.getElement(); 
            }
        
            public void add(E element) {
                Node<E> singlyAdd = new Node<E>(element);
        
                if (tail == null) {
                    head = singlyAdd;
                    tail = singlyAdd;
                } else {
                    tail.setNext(singlyAdd);
                    tail = singlyAdd;
                }     
               
                total++;
            }
        
            public boolean add(int index, E data) {
        
                if (index < 0 || index > size()) {
                    return false;      
                } else {
                    Node<E> singlyAdd = new Node<E>(data);
                    Node<E> singly = head;
        
                    for (int i = 1; i < index && singly.getNext() != null; i++) {
                        singly = singly.getNext();
                    }
        
                    singlyAdd.setNext(singly.getNext());
        
                    singly.setNext(singlyAdd);
                    total++;
                    return true;
                }   
            }       
        
            public void display() {
                if (head == null) {
                    System.out.println("empty list");
                } else {
                    Node<E> current = head;
                    while (current != null) {
                        System.out.print(current.toString());
                        current = current.getNext();
                    }
                }
        
            }
        
            public boolean contains(E data) {
                
                if (head == null) {
                    return false;
                }
        
                if (head.getElement() == data) {
                    System.out.println(head);
                    return true;                                
                }
        
                while (head.getNext() != null) {
                    head = head.getNext();
                    
                    if (head.getElement() == data) {
                        System.out.println(head);                
                        return true;                               
                    }             
        
                } 
        
                return false;         
            }       
        
            private Node<E> removeFirst() {
                if (head == null) {
                    System.out.println("We cant delete an empty list");
                }    
                           
                Node<E> singly = head;            
                head = head.getNext();
                singly.setNext(null);
                total--;
         
                return singly;     
            } 
        
            private Node<E> removeLast() {
               
                Node<E> nodeBefore;
                Node<E> nodeToRemove;     
                
                if (size() == 0) {
                    System.out.println("Empty list");
                }    
                 
                nodeBefore = head;
         
                for (int i = 0; i < size() - 2; i++) {
                  nodeBefore = nodeBefore.getNext();
                }    
               
                nodeToRemove = tail;    
               
                nodeBefore.setNext(null);
                tail = nodeBefore;
                total--;
         
                return nodeToRemove;
            }       
        
            public E remove(int index) {      
              
                E hold = get(index);     
              
                if (index < 0 || index >= size()) {
                    return null;
                } else if (index == 0) { 
                                       
                    removeFirst();    
                    return hold;
                } else {
        
                    Node<E> current = head;
                    for (int i = 1; i < index; i++) {                
                        current = current.getNext();
                    }  
                
                    current.setNext(current.getNext().getNext());
                    total--; 
                    return hold;
                }       
            }       
        
            public int size() {
                return getTotal();
            }             
        
            public void clear() {
        
                while (head.getNext() != null) {    
                    remove(head.getElement());    
                }
        
                remove(head.getElement());    
            }
        
            public int getTotal() {
                return total;
            } 
        }

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,423
    Blog Entries
    7
    Rep Power
    27

    Default Re: Implementing Singly Linked List

    Quote Originally Posted by Robben View Post
    I ran into the dreaded nullpointerexception. I fear that exception.

    I can't seem to fix it though. It only happens when I use the method clear(). The nullpointer exception is pointing at removeLast() method under nodeBefore.setNext(null). It also points at the method clear().
    There's no need to be afraid of that exception; aamof, it's one of the exceptions that is easiest to track down and kill: find two points in your code and name them B and A; at point B everything still is, or still seems, ok; at point A the exception had occurred; put two System.out.println( ... ) statements there, so you can see where your code has been. Now move point B a bit forward, i.e. move it to a position a bit 'later' in your code and run the code again. If your exception still happens after point B but before point A, move B forward again or move A backward and repeat. You're actually narrowing down the position where the exception happens. Before that point there's a bug in your code.

    kind regards,

    Jos
    Robben likes this.
    Build a wall around Donald Trump; I'll pay for it.

  8. #8
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Implementing Singly Linked List

    It seems to me that is you carefully hide the internals of your linked list implementation you could effectively clear the list by simply resetting the head and tail nodes. The GC would "clear" everything else. In other words, the users of your linked list need not know it is a linked list.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  9. #9
    Robben is offline Member
    Join Date
    Feb 2015
    Posts
    67
    Rep Power
    0

    Default Re: Implementing Singly Linked List

    I am almost done with my code but I stumbled upon a method I am not sure how to do.

    Java Code:
    /**
         * Adds each element in the Collection to the end of the linked list.
         *
         * @param c the collection of items to add to the end of the linked list
         */
        @Override
        public void addAll(Collection<? extends E> c) {
          
        }
    The "Collection<? extends E> c" is what confused me. Do I treat as I did when "Node<E> node" gets passed in? Or do I do something like c = Node<>()?

  10. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,423
    Blog Entries
    7
    Rep Power
    27

    Default Re: Implementing Singly Linked List

    No, it just tells you that the Collection contains elements of type (class or interface) E or that the elements extend E. All you have to do in your list is add each element from the Collection to your list:

    Java Code:
    for (T element : theCollection)
       yourList.add(element);
    kind regards,

    Jos
    Robben likes this.
    Build a wall around Donald Trump; I'll pay for it.

  11. #11
    Robben is offline Member
    Join Date
    Feb 2015
    Posts
    67
    Rep Power
    0

    Default Re: Implementing Singly Linked List

    Quote Originally Posted by JosAH View Post
    No, it just tells you that the Collection contains elements of type (class or interface) E or that the elements extend E. All you have to do in your list is add each element from the Collection to your list:

    Java Code:
    for (T element : theCollection)
       yourList.add(element);
    kind regards,

    Jos
    I see, so using your suggestion I did:

    Java Code:
      
        @Override
        public void add(E element) {
            Node<E> singlyAdd = new Node<>(element);
    
            if (tail == null) {
                head = singlyAdd;
                tail = singlyAdd;
            } else {
                tail.setNext(singlyAdd);
                tail = singlyAdd;
            }     
           
            size++;
        }
    
        
        @Override
        public void addAll(Collection<? extends E> c) {
    
            Node<E> singly = tail;
    
            for (E element: c)
                singly.add(element);
          
        }
    but I get a compiling error saying cannot find symbol add(E) method.
    Last edited by Robben; 04-19-2015 at 09:21 PM.

  12. #12
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Implementing Singly Linked List

    Did you realize the return types for add and addAll are wrong for the LinkedList? They are supposed to return a boolean.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  13. #13
    Robben is offline Member
    Join Date
    Feb 2015
    Posts
    67
    Rep Power
    0

    Default Re: Implementing Singly Linked List

    Quote Originally Posted by jim829 View Post
    Did you realize the return types for add and addAll are wrong for the LinkedList? They are supposed to return a boolean.

    Regards,
    Jim
    I am overriding them so that is why I am returning void instead of a boolean.

  14. #14
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Implementing Singly Linked List

    Quote Originally Posted by Robben View Post
    I am overriding them so that is why I am returning void instead of a boolean.
    You can't do that. You must either return the type (or as of Java 1.5) a subtype of the return type.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  15. #15
    Robben is offline Member
    Join Date
    Feb 2015
    Posts
    67
    Rep Power
    0

    Default Re: Implementing Singly Linked List

    But everything works fine except for addAll() method. What I have is an interface named LinkedList and from that interface I am overriding some of the methods like add(), addAll(), and others. The return type from the interface is void so I can't change it to a boolean.

  16. #16
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Implementing Singly Linked List

    Quote Originally Posted by Robben View Post
    But everything works fine except for addAll() method. What I have is an interface named LinkedList and from that interface I am overriding some of the methods like add(), addAll(), and others. The return type from the interface is void so I can't change it to a boolean.
    Ugh. You're using the name LinkedList<E> which I presume is your interface. I read that as the Java API LinkedList which is actually a class. So my mistake. However, the forum discourages using the same names for homegrown classes and interfaces as used in the API as it can lead to confusion. I will now go back and look at the addAll method and see if I spot a problem. It would help if you could include your recent code (including your interface).

    Regards,
    Jim
    Last edited by jim829; 04-19-2015 at 11:25 PM.
    Robben likes this.
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  17. #17
    Robben is offline Member
    Join Date
    Feb 2015
    Posts
    67
    Rep Power
    0

    Default Re: Implementing Singly Linked List

    Quote Originally Posted by jim829 View Post
    Ugh. You're using the name LinkedList<E> which I presume is your interface. I read that as the Java API LinkedList which is actually a class. So my mistake. However, the forum discourages using the same names for homegrown classes and interfaces as used in the API as it can lead to confusion. I will now go back and look at the addAll method and see if I spot a problem. It would help if you could include your recent code (including your interface).

    Regards,
    Jim
    The Interface:

    Java Code:
         
        public interface LinkedList<E> {    
           
            E get(int index);    
            
            void add(E data);        
             
            boolean add(int index, E data);      
    
            void addAll(Collection<? extends E> c);
            
            boolean contains(E data);    
            
            E remove(int index);        
             
            int size();    
            
            void clear();
        
        }
    And what I am having trouble with is the addAll method.

    Java Code:
      
        @Override
        public void add(E element) {
            Node<E> singlyAdd = new Node<>(element);
    
            if (tail == null) {
                head = singlyAdd;
                tail = singlyAdd;
            } else {
                tail.setNext(singlyAdd);
                tail = singlyAdd;
            }     
           
            size++;
        }
    
        
        @Override
        public void addAll(Collection<? extends E> c) {
    
            Node<E> singly = tail;
    
            for (E element: c)
                singly.add(element);
          
        }

  18. #18
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Implementing Singly Linked List

    singly points to an object of class Node. The class Node has no add method.

    Regards,
    Jim
    Robben likes this.
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  19. #19
    Robben is offline Member
    Join Date
    Feb 2015
    Posts
    67
    Rep Power
    0

    Default Re: Implementing Singly Linked List

    So instead of add I should use setNext?

  20. #20
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Implementing Singly Linked List

    No. You are adding multiple elements of a collection. To add them to your current list you need a method which creates a new node with the element to the node and sets the link pointers. And you already have a method that does that. Its called add(). Just don't qualify it (or qualify it with this).

    Regards,
    Jim
    Robben likes this.
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

Page 1 of 2 12 LastLast

Similar Threads

  1. Replies: 6
    Last Post: 05-12-2012, 04:29 AM
  2. Singly Linked List Java implementation
    By xayto in forum New To Java
    Replies: 1
    Last Post: 08-31-2011, 01:36 PM
  3. Trouble with circular singly linked queue
    By somewierdguy in forum New To Java
    Replies: 2
    Last Post: 12-06-2010, 01:48 AM
  4. Implementing a singly linked list
    By Onra in forum New To Java
    Replies: 2
    Last Post: 04-12-2010, 09:19 PM
  5. Trouble Developing Singly Linked Circular List
    By VinceGuad in forum New To Java
    Replies: 14
    Last Post: 02-25-2009, 04:38 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •