Linked list
• If we declare an array as int marks[10], then the array can store a maximum
of 10 data elements but not more than that. Moreover, to make efficient use
of memory, the elements must be stored randomly at any location rather
than in consecutive locations.
• So, there must be a data structure that removes the restrictions on the
maximum number of elements and the storage condition to write efficient
programs.
• Linked list is a data structure that is free from the aforementioned
restrictions.
• A linked list does not store its elements in consecutive memory locations and
the user can add any number of elements to it.
• However, a linked list does not allow random access of data. Elements in a
linked list can be accessed only in a sequential manner. But like an array,
insertions and deletions can be done at any point in the list in a constant
Basic Terminologies
• A linked list, in simple terms, is a linear collection of data elements.
These data elements are called nodes.
• Linked list is a data structure which in turn can be used to implement
other data structures.
• Thus, it acts as a building block to implement data structures such as
stacks, queues, and their variations.
• A linked list can be perceived as a train or a sequence of nodes in which
each node contains one or more data fields and a pointer to the next
node.
• In Fig. 6.1, we can see a linked list in which every node contains two
parts, an integer and a pointer to the next node.
• The left part of the node which contains data may include a simple data
type, an array, or a structure.
• The right part of the node contains a pointer to the next node (or
address of the next node in sequence).
• The last node will have no next node connected to it, so it will store a
special value called NULL.
• In Fig. 6.1, the NULL pointer is represented by X. While programming,
we usually define NULL as –1. Hence, a NULL pointer denotes the end of
the list.
• Linked lists contain a pointer variable START that stores the address
of the first node in the list.
• We can traverse the entire list using START which contains the
address of the first node; the next part of the first node in turn
stores the address of its succeeding node.
• Using this technique, the individual nodes of the list will form a
chain of nodes.
• If START = NULL, then the linked list is empty and contains no nodes.
• In C, we can implement a linked list using the following code:
struct node
{ int data;
struct node *next;
};
• Let us see how a linked list is maintained in the memory. In order to
form a linked list, we need a structure called node which has two
fields, DATA and NEXT. DATA will store the information part and NEXT
will store the address of the next node in sequence. Consider Fig. 6.2.
•
• In the figure, we can see that the variable START is used to store the
address of the first node. Here, in this example, START = 1, so the first data
is stored at address 1, which is H. The corresponding NEXT stores the
address of the next node, which is 4.
• So, we will look at address 4 to fetch the next data item. The second data
element obtained from address 4 is E.
• Again, we see the corresponding NEXT to go to the next node. From the
entry in the NEXT, we get the next address, that is 7, and fetch L as the
data.
• We repeat this procedure until we reach a position where the NEXT entry
contains –1 or NULL, as this would denote the end of the linked list. When
we traverse DATA and NEXT in this manner, we finally see that the linked
list in the above example stores characters that when put together form
the word HELLO.
• Note that Fig. 6.2 shows a chunk of memory locations which range
from 1 to 10. The shaded portion contains data for other
applications. Remember that the nodes of a linked list need not be
in consecutive memory locations. In our example, the nodes for the
linked list are stored at addresses 1, 4, 7, 8, and 10.
Linked Lists versus Arrays
• Both arrays and linked lists are a linear collection of data elements.
But unlike an array, a linked list does not store its nodes in
consecutive memory locations.
• Another point of difference between an array and a linked list is that
a linked list does not allow random access of data. Nodes in a linked
list can be accessed only in a sequential manner. But like an array,
insertions and deletions can be done at any point in the list in a
constant time.
• Another advantage of a linked list over an array is that we can add
any number of elements in the list. This is not possible in case of an
array. For example, if we declare an array as int marks[20], then the
array can store a maximum of 20 data elements only. There is no
such restriction in case of a linked list.
SINGLY LINKED Lists
• A singly linked list is the simplest type of linked list in which every node
contains some data and a pointer to the next node of the same data
type. By saying that the node contains a pointer to the next node, we
mean that the node stores the address of the next node in sequence. A
singly linked list allows traversal of data only in one way. Figure 6.7
shows a singly linked list.
6.2.1 Traversing a Linked List
• Traversing a linked list means accessing the nodes of the list in order to
perform some processing on them. Remember a linked list always
contains a pointer variable START which stores the address of the first
node of the list. End of the list is marked by storing NULL or –1 in the
NEXT field of the last node. For traversing the linked list, we also make
use of another pointer variable PTR which points to the node that is
currently being accessed. The algorithm to traverse a linked list is shown
in Fig. 6.8.
• In this algorithm, we first initialize PTR with the address of START. So now,
PTR points to the first node of the linked list. Then in Step 2, a while loop is
executed which is repeated till PTR processes the last node, that is until it
encounters NULL. In Step 3, we apply the process (e.g., print) to the current
node, that is, the node pointed by PTR. In Step 4, we move to the next node
by making the PTR variable point to the node whose address is stored in the
NEXT field.
• Let us now write an algorithm to count the number of nodes in a linked list.
To do this, we will traverse each and every node of the list and while
traversing every individual node, we will increment the counter by 1. Once
we reach NULL, that is, when all the nodes of the linked list have been
traversed, the final value of the counter will be displayed. Figure 6.9 shows
the algorithm to print the number of nodes in a linked list.
Searching for a Value in a Linked List
• Searching a linked list means to find a particular element in the linked list.
As already discussed, a linked list consists of nodes which are divided into
two parts, the information part and the next part. So searching means
finding whether a given value is present in the information part of the node
or not. If it is present, the algorithm returns the address of the node that
contains the value.
• In Step 1, we initialize the pointer variable PTR with START that
contains the address of the first node.
• In Step 2, a while loop is executed which will compare every node’s
DATA with VAL for which the search is being made. If the search is
successful, that is, VAL has been found, then the address of that
node is stored in POS and the control jumps to the last statement of
the algorithm. However, if the search is unsuccessful, POS is set to
NULL which indicates that VAL is not present in the linked list.
Consider the linked list shown in Fig. 6.11. If we have
VAL = 4, then the flow of the algorithm can be
explained as shown in the figure.
Inserting a New Node in a Linked List
• Case 1: The new node is inserted at the beginning.
• Case 2: The new node is inserted at the end.
• Case 3: The new node is inserted after a given node.
• Case 4: The new node is inserted before a given node
• Let us first discuss an important term called OVERFLOW.
• Overflow is a condition that occurs when AVAIL = NULL or no free memory
cell is present in the system.
• When this condition occurs, the program must give an appropriate message.
Singly linked list or One way chain
• The collection of ordered set of elements.
• The number of elements may vary according to need of the
program.
• A node in the singly linked list consist of two parts: data part
and link part.
• Data part of the node stores actual information that is to be
represented by the node while the link part of the node stores
the address of its immediate successor.
• One way chain or singly linked list can be traversed only in
one direction. In other words, we can say that each node
contains only next pointer, therefore we can not traverse the
list in the reverse direction.
Operations on Singly Linked List
Node Creation
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node *));
Insertion in singly linked list at beginning
• Allocate the space for the new node and store data into the data
part of the node. This will be done by the following statements.
ptr = (struct node *) malloc(sizeof(struct node *));
ptr → data = item
• Make the link part of the new node pointing to the existing first
node of the list. This will be done by using the following
statement.
ptr→next = head;
• At the last, we need to make the new node as the first node of the
list this will be done by using the following statement.
head = ptr;
#include<stdio.h>
#include<stdlib.h>
void beginsert(int);
struct node
{
int data;
struct node *next;
};
struct node *head;
void main ()
{
int choice,item;
do
{
printf("\nEnter the item which you want to insert?\n");
scanf("%d",&item);
beginsert(item);
printf("\nPress 0 to insert more ?\n");
scanf("%d",&choice);
}while(choice == 0);
}
void beginsert(int item)
{
struct node *ptr = (struct node *)malloc(sizeof(struct node *));
if(ptr == NULL
{
printf("\nOVERFLOW\n");
}
else
{
ptr→data = item;
ptr→next = head;
head = ptr;
printf("\nNode inserted\n");
}
}
Insertion in singly linked list at the end
• In order to insert a node at the last, there are two following
scenarios which need to be mentioned.
1. The node is being added to an empty list
2. The node is being added to the end of the linked list
• in the first case,
• The condition (head == NULL) gets satisfied. Hence, we just need
to allocate the space for the node by using malloc statement in C.
Data and the link part of the node are set up by using the
following statements.
ptr→data = item;
ptr → next = NULL;
Head = ptr
In the second case,
• The condition Head = NULL would fail, since Head is not null.
Now, we need to declare a temporary pointer temp in order to
traverse through the list. temp is made to point the first node of
the list.
while (temp→ next ! NULL
temp = temp → next;
• At the end of the loop, the temp will be pointing to the last node
of the list. Now, allocate the space for the new node, and assign
the item to its data part. Since, the new node is going to be the
last node of the list hence, the next part of this node needs to
be pointing to the null. We need to make the next part of the
temp node (which is currently the last node of the list) point to
the new node (ptr) .
temp = head;
while (temp → next ! NULL
{
temp = temp → next;
}
temp→next = ptr;
ptr→next = NULL;
