CODEWITHSUNDEEP
javadata-structureslinked-list
Ashish Gupta
Ashish Gupta

Reputation: 597

Where does the new element in the LinkedList gets added? in after the head or at the tail?

I had read in some blog that the new node gets added the the front. But when i checked the source code of the linkedList, it adds the node at the last and keeps the head address of the list constant, which should be the ideal behavior.

public boolean add(E e) {
        linkLast(e);
        return true;
}
 void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
 }

Is there any difference in the Node addition behavior of the singly and doubly linked Lists?

Upvotes: 0

Views: 97

Answers (2)

Vitaly
Vitaly

Reputation: 2662

From the documentation:

add(E e)

Appends the specified element to the end of this list.

(my emphasis)

As far as I know, where is no single linked list in java library. You can create your own. And I think the only difference will be in: save or not save back link.

Upvotes: 3

Sorontur
Sorontur

Reputation: 510

the LinkedList implementation of Java is a double linked list. So you can use all of its features. If you look at the Methods you can use, there is a addLast and addFirst which does exactly the name says. And the doc of the add method of the List interface says it falls back to addLast. This should answer your question.

In common in a single linked list addLast is O(n) and in a double linked list it is O(1) since you have a reference to the tail as well. AddFirst is all the time O(1).

Upvotes: 2

Related Questions