Some of the screenshots here come from the author of this best seller book.

Java: LinkedList (which is a Doubly-linked list implementation)
C#: LinkedList (which is a doubly-linked list too)

Thinking of a linked list as a list can be a bit misleading. It’s more like a chain. A linked list is a sequence of elements where one element links to the next one.

Following are the various types of linked list.

  • Simple Linked List − a => b => c – Item navigation is forward only (Simple Linked List).
  • Doubly Linked List − a <=> b <=> c – Items can be navigated forward and backward (Doubly linked list).
  • Circular Linked List − a => b => c => a – Last item contains link of the first element as next and the first element has a link to the last element as previous (Circular Linked List).

Simple Linked List

NODE Data Items Next NODE Data Items NODE Next Data Items NULL

Can contain characters…

Or numbers or whatever you want:

Can be unsorted:


Or sorted:

Can contain duplicates:

Or unique elements:


Simple Linked List Implementation with Node class

Very simple example. You just need a Node object and a list.

The below implementation is NOT an optimal implementation, see the Time Complexity.

Time Complexityå slow linear i.) ADVANTAGC inser\ 9 00) Oln)

Insertion and deletion from the head can be done fast in constant time (O(1)).
Insert an element at the beginning (head) can be done in constant time (O(1)).
If you want to delete from the beginning, again constant time (O(1)).

BUT if you want to add or remove an element at the end, that might require walking your way all the way at the end of the link list at the very last element. That takes linear time (O(N)).

That is why you should be maintaining a tail pointer too to avoid walking through the full list.

Doubly linked list

LinkedList is a doubly-linked list – each node knows its previous entry and its next one. This is fast for inserting after/before a particular node (or the head/tail), but slow at access by index.

Circular Linked List

Circular Linked List is a variation of Linked list in which the first element points to the last element and the last element points to the first element.

Singly Linked List as Circular:

Doubly Linked List as Circular

Next Next Next

Array vs linked lists?

Linked lists don’t have indexes b/c they are not based on Arrays like the Lists are.

You have to work you way through the list in order to get the elements.

That takes linear time (O(N)), so quite a bit slower than using the index of an array, constant time (O(1))

讠 a 讠

List vs Linked list?

LinkedList will have less cost when adding/removing items in the middle of the list. Because the List will have to recreate a new array.

While List can only cheaply add/remove at the END of the list (array – it doesn’t to recreate an array in that case) .

List is better for random access, LinkedList is better for sequential access
LinkedList is only at it’s most efficient if you are accessing sequential data (either forwards or backwards) – random access is relatively expensive since it must walk the chain each time (hence why it doesn’t have an indexer). However, because a List is essentially just an array (with a wrapper) random access is fine.

They have different performance characteristics too:
– LinkedList.AddLast(item) constant time
– List.Add(item) amortized constant time, linear worst case
– LinkedList.AddFirst(item) constant time
– List.Insert(0, item) linear time
– LinkedList.AddBefore(node, item) constant time
– LinkedList.AddAfter(node, item) constant time
– List.Insert(index, item) linear time
– LinkedList.Remove(item) linear time
– LinkedList.Remove(node) constant time
– List.Remove(item) linear time
– List.RemoveAt(index) linear time
– LinkedList.Count constant time
– List.Count constant time
– LinkedList.Contains(item) linear time
– List.Contains(item) linear time
– LinkedList.Clear() linear time
– List.Clear() linear time


0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply