Linked List
It is a special data structure in which data elements are linked to one another. Here, each element is called a node which has two parts
- Info part which stores the information.
- Address or pointer part which holds the address of next element of same
type.
Linked list is also known as self referential structure.
Struct linked_list_node
{
int info;
struct linked_list_node *next ;
};
Syntax of declaring a node which contains two fields in it one is for storing information and another is for storing address of other node, so that one can traverse the list.
Note Last node of a linked list contains NULL value in its address field.
Advantages of Linked List
- Linked lists are dynamic data structure as they can grow and shrink
during the execution time.
- Efficient memory utilisation because here memory is not pre-allocated.
- Insertions and deletions can be done very easily at the desired
Disadvantages of Linked List
- More memory is required, if the number of fields are more.
- Access to an arbitrary data item is time consuming
Types of Linked List
These are different types of linked list as given below
Singly Linked List
In this type of linked list, each node has only one address field which points to the next node. So, the main disadvantage of this type of list is that we can’t access the predecessor of node from the the current node.
Doubly Linked List
Each node of linked list is having two address fields (or links) which help in accessing both the successor node (next node) and predecessor node (previous node).
Circular Linked List
It has address of first node in the link (or address) field of last node.
Key Points
- Null Pointer Address field of the last node contains NULL value to indicate the end of list.
- External Pointer (Start Node) Pointer to the very first node of a linked list, it enables us to access the entire linked list.
- Empty List If the nodes are not present in the list, it is empty list or NULL list. The value of the external pointer/start pointer will be NULL for an emptY list.
Start =NULL;
Circular Doubly Linked List
It has both the previous and next pointer in circular manner.
Operations on Linked Lists
The following operations involve in linked list are as given below
Creation
Used to create a linked list.
Insertion
Used to insert a new node in linked list at the specified position. A new
node may be inserted
- At the beginning of a linked list
- At the end of a linked list
- At the specified position in a linked list
- if ease of empty list, a new node is inserted as a first node. Deletion
This operation is basically used to delete as item (a node). A node may be deleted from the
- Beginning of a linked list.
- End of a linked list.
- Specified position in the list.
Traversing
It is a process of going through (accessing) all the nodes of a linked list from one end to the other end.
Memory Allocation: Garbage Collection in Linked List
There should be some mechanisms
- Which provides unused memory space for new nodes.
- Which makes available the memory space of deleted nodes for future
use.
Situation of Overflow and Underflow
Suppose, someone wants to insert new data into a data structure but there is no available space i.e., the free storage list is empty. This situation is usually called
OVERFLOW. The situation, where one wants to delete data from a data structure that is empty is referred as UNDERFLOW.
If START = NULL and someone still wants to delete data, then UNDERFLOW situation occurs.
Key Points
- Together with the linked lists in memory, a special list is maintained which consists of unused memory cells.
- The special list list has it’s own pointer and is called the “List of Available Space ” or the “Free Storage List ” or the “Free Pool”.
Insertion of a Node at Specific Position in a Linked List
The next pointer field of Node A now points to the new Node N, to which
AVAIL previously pointed. AVAIL now points to the second node in the free pool, to which Node N previously pointed.
The next pointer field of Node N now points to Node B to which Node A
previously pointed. Suppose, we are given the value of LOC, where either LOC is the location of a Node A in a linked list or LOC = NULL.
N = New node whose location is NEW
We need to insert ITEM into list, so that ITEM follows Node A or when LOC = NULL, so that ITEM is first node. If LOC is not NULL, then we let Node N point to Node B (which originally followed Node A) by the
assigment.
LINK [NEW] = LINK [LOC]
and we let Node A point to the new Node N by the assignment. LINK [LOC] = NEW
Deletion from a Linked List
In the above diagram, the three pointer fields are changed as follows
- The next pointer field of Node A now points to Node B, where Node ti
previously pointed.
- The next pointer field of N now points to the original first node in free pool, where AVAIL previously pointed.
- AVAIL new points to the deleted Node Polynomials (An Application of Linked Lists)
A polynomial p(x) = 2x5 — 3x4 — 9x2 + 4, may be represented by list, where
each node corresponds to a non-zero term of p(x).
The information part of the node is divided into two fields representing, the coefficient and the exponent of the corresponding term, respectively. All nodes are linked according to decreasing degree.