Data Structures – Linked List

What is Linked List?

• A linked list is a linear data structure where each element is a separate object.
• Each element (we will call it a node) of a list is comprising of two items – the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.
• A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. Any application which has to deal with an unknown number of objects will need to use a linked list.

Types of Linked list:

1. Singly linked list.
2. Doubly linked list.
3. Circular linked list. where last node of the list points back to the first node (or the head) of the list.

Advantages:

1. A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. Any application which has to deal with an unknown number of objects will need to use a linked list.
2. Using Linked list other data structures such as Stacks and Queues can be implemented easily.
3. Insertion and deletion of element can be done faster compared to array because we dont need to go through each element in the list.

Disadvantages:

1. One disadvantage of a linked list against an array is that it does not allow direct access to the individual elements. If you want to access a particular item then you have to start at the head and follow the references until you get to that item.
2. Another disadvantage is that a linked list uses more memory compare with an array – we require extra 4 bytes (on 32-bit CPU) to store a reference to the next node.