Linked List

What would you explain linked list to a person?
Consider a linked list to be a train where Engine is the head and you have flexibility to join locomotives or remove them . Each locomotives of the train is analogous to data node in a linked list, locomotives are connected in manner where person can go from locomotives to locomotives as you can traverse a linked list. 

Insertion, deletion: Let's say train company find a locomotive to be faulty. They remove(delete) the faulty locomotive and insert a working locomotive

This would be a doubly linked list, for singly linked list you can put a restriction that person can traverse from head to last locomotives only.

• In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. 

• Unlike arrays , linked list can grow or shrink in size ( size of arrays is fixed e.g. a[10]). There is ease in doing insertion and deletion in linked list than arrays. In arrays , we have to shift elements during any insertion or deletion (if sorting is maintained).

• Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.
• That vectors/arrays are almost always faster because hardware memory access is optimized (caching, prefetch) for accessing contiguous addresses.
•  It takes 4- 6 times the memory and 600-1000 times the CPU of a vector.

Uses of Linked List :-

• Linked lists can be used to implement stacks, queues, graphs, etc.
• Linked lists let you insert elements at the beginning and end of the list in O(1) time. This makes for efficient implementations of stacks, queues.
• Linked lists also remove the overhead of bothering about the size of the data structure. The size need not to be known in advance.
• They can also be used for the adjacency list representation of graphs.
• Hash tables with chaining is also possible.

More topics in linked list :-

Introduction and Implementation of linked list

Traversing a linked list

Searching in Linked list

Insertion in Linked list

Deletion in linked list

Reversing Linked list

Header linked list

Circular Linked list

Doubly Linked list