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

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).

 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

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.

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 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.

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))

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:
Append
– List.Add(item) amortized constant time, linear worst case
Prepend
– List.Insert(0, item) linear time
Insertion
– List.Insert(index, item) linear time
Removal
– List.Remove(item) linear time
– List.RemoveAt(index) linear time
Count
– List.Count constant time
Contains
– List.Contains(item) linear time
Clear