Single linked list in java

Question

In the following code, I am trying to understand one thing in the insertFirst() method that

Why is the last statement first =newLink; and not first.next=new Link; Will it be wrong? Isn't there a "next" in first?

I know this code is right and I know that a node needs to be inserted at the beginning and all, but I need help understanding just one statement.

Is first =newLink; and first.next=new Link; not the same thing?

public class LinkedList {

    private Link first;

    public LinkedList()
    {
        first = null;
    }

    public boolean isEmtpy()
    {
        return(first==null);
    }

    public void insertFirst(int id, int dd)
    {
        Link newLink=new Link(id,dd);
        newLink.next=first;
        first =newLink;
    }


}

remember that first was already null. it doesn't have a next. — euphoria83
– euphoria83, Commented Mar 29, 2011 at 18:40

Ernest Friedman-Hill · Accepted Answer · 2011-03-29 18:34:20Z

3

No, it's right: the list inserts new links at the beginning. The old "first" becomes the new link's "next", and the new link is the new "first".

answered Mar 29, 2011 at 18:34

Ernest Friedman-Hill

81.9k11 gold badges158 silver badges192 bronze badges

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

3 Comments

user665319 Over a year ago

I know this code is right and I know that a node needs to be inserted at the beginning and all, but I need help understanding just one statement. Is first =newLink; and first.next=new Link; not the same thing?

Ernest Friedman-Hill Over a year ago

No. Think of each Link as a box which holds two things: a number, and a pointer to another box "next". The list itself has a pointer named "first" which points to the front of the list, and each node then points to its neighbor. If we did "newLink.next = first.next; first.next=newLink" that would mean that first is pointing to a box (call it "A") and then A is pointing to the new link, and the new link is pointing to what "first" was originally pointing to. On the other hand, "newLink.next = first; first = newLink" means that first is pointing to the new link, and newLink is pointing to A.

Ernest Friedman-Hill Over a year ago

"first" is a pointer to the first link -- the first box. Only the boxes have numbers in them.

Isaac Truett · Accepted Answer · 2011-03-29 18:45:33Z

2

Why is the last statement first =newLink; and not first.next=new Link;

Because you're inserting a new first element and the "next" element is the old first element, which was set on the previous line.

Is first =newLink; and first.next=new Link; not the same thing?

No. first is the first and first.next is the second.

edited Mar 29, 2011 at 18:45

answered Mar 29, 2011 at 18:36

Isaac Truett

8,8741 gold badge31 silver badges49 bronze badges

1 Comment

user665319 Over a year ago

Thanks that is the answer I was looking for. Just about that one statement mainly.

lukastymo · Accepted Answer · 2011-03-29 18:35:13Z

0

This is because you want to put new element to the beginning, so you must set new element to the head of list and this element should point on "old-head", and then you have:

new_elemnt->old_head->...

answered Mar 29, 2011 at 18:35

lukastymo

27k14 gold badges56 silver badges66 bronze badges

Comments

Oswald · Accepted Answer · 2011-03-29 18:37:58Z

0

LinkedList::first is not a guard element. It really points to the first element of the list. If LinkedList::first == null, then the list is empty. If Link::next == null, then it's the last element (the null is called a guard element in this case).

answered Mar 29, 2011 at 18:37

Oswald

31.8k3 gold badges46 silver badges72 bronze badges

Comments

Ajay Kumar · Accepted Answer · 2017-08-29 04:30:24Z

Simple example of SingleLinkedList in Java

    package com.ds;

    public class SingleLinkedList {


        private Node head;

        public static void main(String[] args) {
            SingleLinkedList linkedList = new SingleLinkedList();
            linkedList.insert(5);
            linkedList.insert(15);
            linkedList.insert(45);
            linkedList.insert(55);
            linkedList.insert(58);
            linkedList.insert(25);

            // Print value of Single Linked list.
            linkedList.print();
            // delete node from tail side.
            linkedList.delete();
            linkedList.delete();
            linkedList.delete();
            linkedList.delete();
            linkedList.delete();
            /*linkedList.delete();
            linkedList.delete();
            linkedList.delete();
            linkedList.delete();*/
            linkedList.print();

        }

        SingleLinkedList() {
            head = null;
        }

        void insert(int val) {
            Node temp = new Node();
            temp.data = val;
            temp.next = null;
            if (head == null) {
                head = temp;
            } else {
                Node k = head;
                while (k.next != null) {
                    k = k.next;
                }
                k.next = temp;
            }
        }

        // delete from tail.
        void delete() {
            // if it's first node
            if (head == null || head.next == null) {
                head = null;
            } else {
                Node n = head;
                Node t = head;
                while (n.next != null) {
                    t = n;
                    n = n.next;
                }
                t.next = null;
            }

        }

        void print() {
            Node k = head;
            while (k != null) {
                System.out.println(k.data);
                k = k.next;
            }
        }

       Node reverse() {
            Node h = head;
            Node p = null;
            Node t = null;
            while (h != null) {
                t = h.next;
                h.next = p;
                p = h;
                h = t;
            }
            return p;
        }

        class Node {
            private int data;
            private Node next;
        }
    }

Collectives™ on Stack Overflow

Single linked list in java

5 Answers 5

3 Comments

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related