Linked list code in Java

Question

I was watching a video on data structures and algorithms offered here

There firstly code for linked list was written as

public class SListNode{
    public Object item;
    public SListNode next;
    public SListNode(Object item,SListNode next){
        this.item=item;
        this.next=next; 
    }
    public SListNode(Object item){
        this(item,null);
    }
    public void insertAfter(Object item){
        next=new SListNode(item,next);  
    }
    public SListNode nth(int position){
        if (position==1){
            return this;
        }
        else if ((position<1)|| next==null){
            return null;
        }
        else{
            return next.nth(position-1);
        }

    }

Then the lecturer said that there are two problems associated with this implementation.

1)if X and Y refer to the same list and if a new item was inserted to x , y doesn't get updated.I think this can be checked by

public static void main (String args[]){
        SListNode l1=new SListNode("milk",new SListNode(0,new SListNode(1)));
        SListNode l2=l1;
        l2=new SListNode("soap",l2);
        System.out.println(l1.item+ " "+l1.next.item+ " " +l1.next.next.item);
        System.out.println(l2.item+ " "+l2.next.item+ " " +l2.next.next.item);

2)when creating an empty list.

Therefore as a solution separate SListClass that maintains head of list was created.

public class SList{
    privte SListNode head;
    private int size;
    public SList(){
        head=null;
        size=0;
    }
    public void insertFront(Object item){
    head=new SListNode(item,head);
    }
}

I don't understand how to work with SList class.
How to create a linked list with this class?

How is SListNode and Slist classes are connected and how can the methods of SlistNode be called from SList?
Also how has this new implementation provide a solution to earlier problem of if X and Y refer to the same list and if a new item was inserted to x , y doesn't get updated.

I am new to programming and Java therefore a clear explanation would be great

I have only quickly scanned the question but X and Y will only differ (with a linked list) if the head element is updated because the other list (the one not updated) will still refer to the "second" element. Storing the head in a separate class bypasses this issue as X and Y both refer to the head-wrapper. — nablex
– nablex, Commented Apr 29, 2014 at 13:46

Christian · Accepted Answer · 2014-04-29 14:18:11Z

1

What you have here is a classic LinkedList implementation. SListNode represents a single node of the list, while SList basically represents the entire list. It manages the head of your list (and usually some other attributes such as the list's size, maybe a reference to the list's tail etc.).

What you would usually do is use ONLY the SList in your code, which than encapsulates and manages your single SListNodes. To do that SList needs "dictionary methods" for inserting, deleting, finding etc. objects in your list (which are encapsulated inside your SListNode elements managed by your SList). That is why I think the SList-class you have above is not complete yet.

Your code example

SListNode l1=new SListNode("milk",new SListNode(0,new SListNode(1)));
SListNode l2=l1;
l2=new SListNode("soap",l2);

does not show what the instructor says. What you do here is create one SListNode which references l1. Then you create a NEW SListNode-Object and point l2 to it (and then you create a "circular reference" to itself). Of course l1 and l2 are no longer referencing the same object!

edited Apr 29, 2014 at 14:18

answered Apr 29, 2014 at 14:05

Christian

1,5861 gold badge22 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

clarkson Over a year ago

SList needs methods means should I need to have the insertAfter(),nth() methods in SListNode in SList and not in SlistNode

Christian Over a year ago

No. Methods in SList do not replace methods in SListNode. Say SList has a method insertAtEnd(Object o) then you would first find the end of your list (which is a reference to an SNode-Object. Then you would call your SListNode-method insertAfter() on that very node (e.g. SListNode tail = //find tail here; tail.insertAfter(Object o);)

clarkson Over a year ago

If I want to create a new linked list with items 34,"a",100 how is this done?Is it done by SListNode l_0=new SListNode(34,new SListNode("a",new SListNode(100)));.If so then how is the connection with head in SList is made with this linked list l_0

Christian Over a year ago

No. You do not want to use the Nodes in your productive code. What you would do is create a new list (e.g. SList l = new SList();) and then add elements to that list (e.g. SList.insertEnd("milk"); / SList.insertAfter("apple", "milk"); / SList.insertFront("milk");). Your SList needs to implement those dictionary methods. SList can then cycle through your entire list (by calling the proper methods of SListNode, e.g. next()) and perform the proper actions.

Christian Over a year ago

Please understand the difference between your class SList (representing the entire List) and your class SListNode (representing the elements your list contains of. Every Node has a payload (i.e. data) and a successor). Please do not forget to rate and accept my answer.

|

Collectives™ on Stack Overflow

Linked list code in Java

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related