CODEWITHSUNDEEP
javalinked-list
phoenix
phoenix

Reputation: 3621

linked list implementation, adding at head or adding at tail?

I have seen many implementations of linked list adding at head then updating the head reference or not modifying the head reference and adding at the tail updating it each time. Is there an obvious benefit of one vs the other? Which one is the preferred way of implementation?

Upvotes: 2

Views: 4198

Answers (3)

Thilo
Thilo

Reputation: 262824

The absolute simplest implementation of a linked list can only (efficiently) add at the head. In order to add to the tail, you need a second pointer that points to the current last element.

Users probably want to be able to add to either end, as well as be able to query the list length in constant time, and traverse the list from tail to head (meaning you need a double-linked list), so a reasonable default implementation should support that (just like the one in java.util does).

You'd only be using single-linked lists if you can justify the limited functionality and get some real benefit in return (such as tail-sharing to reduce storage requirements). ConcurrentLinkedQueue appears to be single-linked to allow for lock-free concurrency. The tradeoff of not being able to know the current length is mentioned in the Javadocs.

Upvotes: 1

Nulldevice
Nulldevice

Reputation: 4006

java.util.LinkedList implements both functionalities. It makes it a universal - it is possible to use it as a queue (FIFO) and as a stack (LIFO)

Upvotes: 0

corsiKa
corsiKa

Reputation: 82589

There's no benefit at all. In fact, the only thing that makes the head the head and the tail the tail is that we call one the head and one the tail. You could replace head with tail, and tail with head, and you'd have the same exact list, except it would be "backwards." (This does assume a doubly linked list...)

It's kinda like matter and antimatter...

Upvotes: 1

Related Questions