How do you mean by linked list explain different types of linked list used in data structure with suitable example.
Linked lists are the best and simplest example of a dynamic data structure that uses pointers for its implementation. However, understanding pointers is crucial to understanding how linked lists work, so if you’ve skipped the pointers tutorial, you should go back and redo it. You must also be familiar with dynamic memory allocation and structures. Essentially, linked lists function as an array that can grow and shrink as needed, from any point in the array.
Linked lists have a few advantages over arrays: –
- Items can be added or removed from the middle of the list
- There is no need to define an initial size
However, linked lists also have a few disadvantages: –
- There is no “random” access – it is impossible to reach the nth item in the array without first iterating over all items up until that item. This means we have to start from the beginning of the list and count how many times we advance in the list until we get to the desired item.
- Dynamic memory allocation and pointers are required, which complicates the code and increases the risk of memory leaks and segment faults.
- Linked lists have a much larger overhead over arrays, since linked list items are dynamically allocated (which is less efficient in memory usage) and each item in the list also must store an additional pointer.
What is a linked list?
A linked list is a set of dynamically allocated nodes, arranged in such a way that each node contains one value and one pointer. The pointer always points to the next member of the list. If the pointer is NULL, then it is the last node in the list.
A linked list is held using a local pointer variable which points to the first item of the list. If that pointer is also NULL, then the list is considered to be empty.
Type of linked list: –
Singly linked list: – Singly linked lists contain nodes which have a data field as well as a ‘next’ field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.
A singly linked list whose nodes contain two fields: an integer value and a link to the next node
Doubly linked list: – In a ‘doubly linked list’, each node contains, besides the next-node link, a second link field pointing to the ‘previous’ node in the sequence. The two links may be called ‘forward(‘s’) and ‘backwards’, or ‘next’ and ‘prev'(‘previous’).
A doubly linked list whose nodes contain three fields: an integer value, the link forward to the next node, and the link backward to the previous node
A technique known as XOR-linking allows a doubly linked list to be implemented using a single link field in each node. However, this technique requires the ability to do bit operations on addresses, and therefore may not be available in some high-level languages.
Many modern operating systems use doubly linked lists to maintain references to active processes, threads, and other dynamic objects. A common strategy for rootkits to evade detection is to unlink themselves from these lists.
Circular Linked list: – In the last node of a list, the link field often contains a null reference, a special value used to indicate the lack of further nodes. A less common convention is to make it point to the first node of the list; in that case the list is said to be ‘circular’ or ‘circularly linked’; otherwise it is said to be ‘open’ or ‘linear’.
A circular linked list
In the case of a circular doubly linked list, the only change that occurs is that the end, or “tail”, of the said list is linked back to the front, or “head”, of the list and vice versa.
Circular Queue Data Structure
In a standard queue data structure re-buffering problem occurs for each dequeue operation. To solve this problem by joining the front and rear ends of a queue to make the queue as a circular queue
Circular queue is a linear data structure. It follows FIFO principle.
- In circular queue the last node is connected back to the first node to make a circle.
- Circular linked list fallow the First In First Out principle
- Elements are added at the rear end and the elements are deleted at front end of the queue
- Both the front and the rear pointers points to the beginning of the array.
- It is also called as “Ring buffer”.
- Items can inserted and deleted from a queue in O (1) time.
Circular Queue can be created in three ways they are: –
- Using single linked list
- Using double linked list
- Using arrays
Algorithm for Insertion in a circular queue: –
Insert CircularQueue ( ) 1. If (FRONT == 1 and REAR == N) or (FRONT == REAR + 1) Then 2. Print: Overflow 3. Else 4. If (REAR == 0) Then [Check if QUEUE is empty] (a) Set FRONT = 1 (b) Set REAR = 1 5. Else If (REAR == N) Then [If REAR reaches end if QUEUE] 6. Set REAR = 1 7. Else 8. Set REAR = REAR + 1 [Increment REAR by 1] [End of Step 4 If] 9. Set QUEUE[REAR] = ITEM 10. Print: ITEM inserted [End of Step 1 If] 11. Exit
Algorithm for Deletion in a circular queue: –
Delete CircularQueue ( ) 1. If (FRONT == 0) Then [Check for Underflow] 2. Print: Underflow 3. Else 4. ITEM = QUEUE[FRONT] 5. If (FRONT == REAR) Then [If only element is left] (a) Set FRONT = 0 (b) Set REAR = 0 6. Else If (FRONT == N) Then [If FRONT reaches end if QUEUE] 7. Set FRONT = 1 8. Else 9. Set FRONT = FRONT + 1 [Increment FRONT by 1] [End of Step 5 If] 10. Print: ITEM deleted [End of Step 1 If] 11. Exit