Chapter 4: Linked List Data Structure
What is Linked List ? Explain.
A linked list is a linear data structure where each element is a separate object. Each element (Node) of a list comprises 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.
Advantages of Linked List
- Insertion and deletion operations can be easily implemented.
- 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.
Disadvantages of Linked List
- 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.
- Linked list uses more memory compare with an array - we extra 4 bytes (on 32-bit CPU) to store a reference to the next node.
Types of Linked Lists
- Singly linked list
- Doubly linked list
- Circular linked list
Singly Linked List
Singly linked list contains node with two parts data part and reference part. Data part contains data and reference part points to the next node in the sequence.
Doubly Linked List
Double linked list contains node with three parts one data part and two reference parts. Data part contains data, first reference part points to previous node in the sequence and another reference part points to the next node in the sequence.
Circular Linked List
Circular linked list contains node with two parts data part and reference part. Data part contains data and reference part points to the next node in the sequence. Also last node points back to first node (head) of the list.
Linked List Operations
Following are the important operations performed on linked lists
- Insert a node at the begging of the list
- Insert a node at the end of the list
- Delete a node from the list
We can also perform common operations like search and display
Posts
