Linked list

UNIT 3

Linked list

​

• 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.
• 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.

Linked list

• 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. A NULL pointer denotes the end of the list. Since in a linked list, every node contains a pointer to another node which is of the same type, it is also called a self-referential data type.
• Linked lists contain a pointer variable START that stores the address of the first node in the list.
• 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;

};

• Note Linked lists provide an efficient way of storing related data and perform basic operations such as insertion, deletion, and updation of information at the cost of extra space required for storing address of the next node.

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.

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.
• Figure 6.9 shows the algorithm to print the number of nodes in a 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�

• Take four cases and then see how insertion is done in each case.
• 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.

• In Step 1, we first check whether memory is available for the new node. If the free memory has exhausted, then an OVERFLOW message is printed.
• Otherwise, if a free memory cell is available, then we allocate space for the new node. Set its DATA part with the given VAL and the next part is initialized with the address of the first node of the list, which is stored in START.
• Now, since the new node is added as the first node of the list, it will now be known as the START node, that is, the START pointer variable will now hold the address of the NEW_NODE. Note the following two steps:
• Step 2: SET NEW_NODE = AVAIL
• Step 3: SET AVAIL = AVAIL -> NEXT
• These steps allocate memory for the new node. In C, there are functions like malloc(), alloc, and calloc() which automatically do the memory allocation on behalf of the user.

Deleting a Node from a Linked List�

• In this section, we will discuss how a node is deleted from an already existing linked list. We will
• consider three cases and then see how deletion is done in each case.
• Case 1: The first node is deleted.
• Case 2: The last node is deleted.
• Case 3: The node after a given node is deleted.
• Before we describe the algorithms in all these three cases, let us first discuss an important term
• called UNDERFLOW. Underflow is a condition that occurs when we try to delete a node from a linked
• list that is empty. This happens when START = NULL or when there are no more nodes to delete.

Deleting the First Node from a Linked List

Deleting the Last Node from a Linked List

CIRCULAR LINKED LISTs

Inserting a New Node in a Circular Linked List

• How a new node is added into an already existing linked list. Two cases are discussed and see how insertion is done in each case.
• Case 1: The new node is inserted at the beginning of the circular linked list.
• Case 2: The new node is inserted at the end of the circular linked list.
• Inserting a Node at the Beginning of a Circular Linked List
• Consider the linked list shown in Fig. 6.29. Suppose we want to add a new node with data 9 as
• the first node of the list. Then the following changes will be done in the linked list.

Inserting a Node at the End of a Circular Linked List

DOUBLY LINKED LISTS

• A doubly linked list or a two-way linked list is a more complex type of linked list which contains
• a pointer to the next as well as the previous node in the sequence. Therefore, it consists of three
• parts—data, a pointer to the next node, and a pointer to the previous node as shown in Fig. 6.37.

Inserting a New Node in a Doubly Linked List

• Let us discuss how a new node is added into an already existing doubly linked list. We will take four cases and then see how insertion is done in each case.
• 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.