List
A list can be defined as a finite collection of data elements. The elements that constitute the list are known as list items. In general, a list can be defined as
L={a1,a2,a3,....,an }
Where a1,a2,a3,....,an = ai are list items
A list is a very common data structure that has a wide variety of applications.
For implementation, we can assume that the list items belong to the same type of items (homogeneous nature) or of the same data types.
A list can be treated as a finite collection of homogeneous data items. Such a list can be implemented using arrays.
Operations:
The common operations that can be characterised for list data items are as follows:
Checking for an empty list
Checking for a full list
Inserting a new element
Deleting an element
Searching for a particular element
Finding the length of a list
Merging list
Concatenation of a list
List traversal
Displaying a list
Need for Dynamic Implementation of List
When a List is implemented using an Array, the problem of overflow is always associated with it. This is because an array is a finite structure. Its size must be declared in advance.
For example, if an array is declared with size 10, it can store only 10 elements. When all the 10 slots are occupied and we try to insert a new element, an overflow condition occurs. This can happen even when free memory is available in the computer system.
One solution is to declare an array with a large size. This can postpone the overflow problem. However, it may result in memory wastage because the memory allocated to the array remains reserved for that array and cannot be easily used for another purpose.
Therefore, we need an implementation in which:
The maximum size of the List is not fixed in advance.
A new element can be inserted whenever free memory is available.
When an element is deleted, the memory occupied by it should be released.
The released memory should be returned to the computer system so that it can be used for other purposes.
This is possible through dynamic memory allocation.
In the C language, dynamic memory allocation is performed using pointers and functions such as:
malloc() — allocates memory dynamically.
free() — releases dynamically allocated memory.
Thus, a linked list is commonly used to implement a List dynamically because it can grow and shrink according to the available memory.
Linked List
A linked list can be defined as a collection of nodes where each node consists of two parts:
Info Part or Data Part
Next Part or Pointer Part or Next Address Part
In a linked list, the physical and logical ordering of nodes need not be the same.
For example, nodes may be stored at different memory locations, but the Next pointer connects them in the required logical sequence.
Operations on a Linked List
Declaration of a linked-list node.
Initialization of the linked list.
Checking whether the list is empty.
Insertion of a node into the linked list.
Deletion of a node from the linked list.
Searching for an item in the linked list.
Traversing the linked list.
Concatenation of two linked lists.
Merging two linked lists.
Counting the number of nodes in the linked list.
Insertion at different positions:
At the beginning
At the end
Before a selected node
After a selected node
At a specified position
Deletion from different positions:
From the beginning
From the end
From anywhere in the list
Updating the information stored in a node.
Advantages of a Linked List over an Array-Based List
1. No Fixed Size
A linked list does not require a fixed size to be declared in advance.
Memory is allocated dynamically as new nodes are required.
2. Easy Insertion
A new node can be inserted by changing the required links.
Existing nodes do not need to be shifted, as they are in an array.
3. Easy Deletion
A node can be deleted by changing the links between the surrounding nodes.
Other nodes do not need to be shifted.
4. Better Memory Utilisation
Memory is allocated when a node is required.
Therefore, unused pre-allocated array space can be avoided.
However, each node requires additional memory for storing the pointer.
5. Dynamic Structure
The size of a linked list can grow or shrink during program execution, subject to the availability of memory.
6. Useful for Implementing Other Data Structures
Linked lists can be used to implement several other data structures, such as:
Linked Stack
Linked Queue
Sparse Matrix
Polynomial Representation
Important Note about Overflow
It is not technically correct to say: "A linked list has no overflow problem."
A linked list can also become full when the system is unable to allocate additional memory. A more accurate statement is:
"A linked list does not have the fixed-size overflow problem associated with a statically allocated array."
Thus, an array may report overflow when its allocated capacity is exhausted, even if additional memory is available elsewhere in the system. A linked list can dynamically request memory for new nodes, provided sufficient memory is available.
Algorithm: Insertion in Between a Linked List
Purpose: Insert a new node after the node containing the value val.
Algorithm:
ptr = list
While (ptr != NULL), repeat Steps 3 to 5.
If (Info(ptr) == val), then:
x = new node
Read(Info(x))
Next(x) = Next(ptr)
Next(ptr) = x
Exit (if only one insertion is required)
ptr = Next(ptr)
End While
End of Algorithm
The two important statements are:
Next(x) = Next(ptr)
Next(ptr) = x
This first connects the new node X to the next node, and then connects ptr to X.
Important: If the algorithm is intended to insert only one node, use Exit after insertion. Otherwise, the traversal may continue and potentially perform additional insertions.
Algorithm: Insertion of a Data Item Before a Selected Node
Purpose: Insert a new node before the node containing the selected value val in a singly linked list.
Algorithm:
ptr = list
prev = NULL
While (ptr != NULL), repeat Steps 4 to 7.
If (Info(ptr) == val), then:
x = new node
Read(Info(x))
Next(x) = ptr
If (prev == NULL), then:
list = x
Otherwise:
Next(prev) = x
Exit
prev = ptr
ptr = Next(ptr)
End While
End of Algorithm
Algorithm: Deletion of a Node from a Linked List
Purpose: Delete the node containing a selected value val from a singly linked list.
Algorithm:
ptr = list
prev = NULL
If (list == NULL), then
Print "Underflow / List is Empty"
Go to Step 9
While (ptr != NULL), repeat Steps 5 to 7.
If (Info(ptr) == val), then:
If (prev == NULL), then
list = Next(ptr)
Otherwise,
Next(prev) = Next(ptr)
Free(ptr)
Exit
prev = ptr
ptr = Next(ptr)
End While
Print "Node not found"
End of Algorithm