Linked List�

By

Mr. Abhijit T. Somnathe

What is Link List?

• linked list is a linear data structure.
• It contains nodes. Each node contains two parts, i.e. DATA part and LINK part.
• The data contains elements, and Link contains address of another node.

​

​

Representation of Link List

Link List V/s Array

Types of Linked List

• Following are the various types of linked list.
• Single linked list
• Double linked list
• Circular linked list

​

Single Linked List

• A single linked list is one in which all nodes are linked together in some sequential manner.
• Each node has only one link part.
• Each link part contains the address of the next node in the list.
• Link part of the last node contains NULL value which signifies the end of the node.

​

Double Linked List

• A single linked list has disadvantage that it can traverse it in one direction.
• Many applications require searching backward and forward travelling sections of a list.
• A two way list is a linear collection of data elements called nodes.

Double Linked List

• Each node is divided into three parts. There are two link parts and one data part.

​

Circular Linked List

• A circular linked list is one which has no beginning and no ending.
• The null pointer in the last node of a linked list is replaced with the address of its first node.

​

Basic Operations on Linked List

• Traversal: To travel through all the nodes one after another.
• Insertion: To add a node at the given position.
• Deletion: To delete a node.
• Searching: To search an element(s) by value.
• Updating: To update a node.
• Sorting: To arrange nodes in a linked list in a specific order.
• Merging: To merge two linked lists into one.

Insertion of node in Linked List

• A node can be added in three ways
• At the front of the linked list
• After a given node.
• At the end of the linked list.

Add a node at the front

• Since there is no need to find the end of the list. If the list is empty, we make the new node as the head of the list. Otherwise, we have to connect the new node to the current head of the list and make new node, head of the list.

​

Add a node after a given node

• We can give a temporary pointer to a node, and the new node is inserted after the given node.

​

Add a node at the end

• In such case the new node is going to be the last node.
• Set the next pointer of the new node to be NULL.

​

Linked List node Deletion

• To delete a node from a linked list, we need to do these steps
• Find the previous node of the node to be deleted.
• Change the next pointer of the previous node
• Free the memory of the deleted node.

Linked List node Deletion

• In node deletion, if the first node is to be deleted, we need to update the head of the linked list.

​

Implementation of Stack using Singly Linked List

• The major problem with the stack implemented using an array is, it works only for a fixed number of data values.
• The amount of data must be specified at the beginning of the implementation.
• Stack implemented using an array is not suitable, when we don't know the size of data which we are going to use.
• A stack data structure can be implemented by using a linked list data structure.

Implementation of Stack using Singly Linked List

• The stack implemented using linked list can work for an unlimited number of values.
• Stack implemented using linked list works for the variable size of data.
• So, there is no need to fix the size at the beginning of the implementation.
• Stack implemented using linked list can organize as many data values as we want.

Implementation of Stack using Singly Linked List

• So, instead of using array, we can also use linked list to implement stack.
• Linked list allocates the memory dynamically.
• However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.

Implementation of Stack using Singly Linked List

• In linked list implementation of stack, the nodes are maintained non-continuously in the memory.
• Each node contains a pointer to its immediate successor node in the stack.
• The top most node in the stack always contains null in its address field.
• Lets discuss the way in which, each operation is performed in implementation of stack.

Implementation of Stack using Singly Linked List

• In linked list implementation of a stack, every new element is inserted as 'top' element.
• Every newly inserted element is pointed by 'top'.
• Whenever we want to remove an element from the stack, simply remove the node which is pointed by 'top' by moving 'top' to its previous node in the list.
• The next field of the first element must be always NULL.

Implementation of Stack using Singly Linked List

​

​

​

​

​

​

​

​

• In the above example, the last inserted node is 99 and the first inserted node is 25. The order of elements inserted is 25, 32,50 and 99.

Adding a node to the stack (Push Operation)

• Adding a node to the stack is referred to as push operation.
• Pushing an element to a stack in linked list implementation is different from that of an array implementation.
• In order to push an element onto the stack, the following steps are involved.
• Create a node first and allocate memory to it.

Adding a node to the stack (Push Operation)

Adding a node to the stack (Push Operation)

• If the list is empty then the item is to be pushed as the start node of the list. This includes assigning value to the data part of the node and assign null to the address part of the node.
• If there are some nodes in the list already, then we have to add the new element in the beginning of the list (not to violate the property of the stack). For this purpose, assign the address of the starting element to the address field of the new node and make the new node, the starting node of the list.

Adding a node to the stack (Push Operation)

Deleting a node from the stack (POP operation)

• Deleting a node from the top of stack is referred to as pop operation.
• Deleting a node from the linked list implementation of stack is different from that in the array implementation.
• In order to pop an element from the stack, we need to follow the following steps:

Deleting a node from the stack (POP operation)

• Check for the underflow condition: The underflow condition occurs when we try to pop from an already empty stack. The stack will be empty if the head pointer of the list points to null.
• Adjust the head pointer accordingly: In stack, the elements are popped only from one end, therefore, the value stored in the head pointer must be deleted and the node must be freed. The next node of the head node now becomes the head node.

Implementation of Queue using Singly Linked List

• Although, the technique of creating a queue using array is easy, but there are some drawbacks of using this technique.
• Memory wastage : The space of the array, which is used to store queue elements, can never be reused to store the elements of that queue because the elements can only be inserted at front end and the value of front might be so high so that, all the space before that, can never be filled.

Implementation of Queue using Singly Linked List

​

​

​

• In the above figure, a queue of size 10 having 3 elements, is shown. The value of the front variable is 5, therefore, we can not reinsert the values in the place of already deleted element before the position of front. That much space of the array is wasted and can not be used in the future (for this queue).

Implementation of Queue using Singly Linked List

• Deciding the array size: On of the problem with array implementation is the size of the array which requires to be declared in advance. Due to the fact that, the queue can be extended at runtime depending upon the problem, the extension in the array size is a time taking process and almost impossible to be performed at runtime since a lot of reallocations take place. Due to this reason, we can declare the array large enough so that we can store queue elements as enough as possible but the main problem with this declaration is that, most of the array slots (nearly half) can never be reused. It will again lead to memory wastage.

​

Implementation of Queue using Singly Linked List

• Due to the drawbacks discussed above, the array implementation can not be used for the large scale applications where the queues are implemented.
• One of the alternative of array implementation is linked list implementation of queue.
• In a linked queue, each node of the queue consists of two parts i.e. data part and the link part.
• Each element of the queue points to its immediate next element in the memory.

Implementation of Queue using Singly Linked List

• In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer.
• The front pointer contains the address of the starting element of the queue while the rear pointer contains the address of the last element of the queue.
• Insertion and deletions are performed at rear and front end respectively. If front and rear both are NULL, it indicates that the queue is empty.

Implementation of Queue using Singly Linked List

• The linked representation of queue is shown in the following figure.

​

Operation on Linked Queue

• There are two basic operations which can be implemented on the linked queues.
• The operations are Insertion and Deletion.

​

• Insert operation
• The insert operation append the queue by adding an element to the end of the queue.
• The new element will be the last element of the queue.

Operation on Linked Queue

• There can be the two scenario of inserting this new node ptr into the linked queue.
• In the first scenario, we insert element into an empty queue.
• In this case, the condition front = NULL becomes true.
• Now, the new element will be added as the only element of the queue and the next pointer of front and rear pointer both, will point to NULL.

Operation on Linked Queue

• In the second case, the queue contains more than one element. The condition front=NULL becomes false.
• In this scenario, we need to update the end pointer rear so that the next pointer of rear will point to the new node pointer.
• Since, this is a linked queue, hence we also need to make the rear pointer point to the newly added node pointer. We also need to make the next pointer of rear point to NULL.

Operation on Linked Queue

• Deletion Operation
• Deletion operation removes the element that is first inserted among all the queue elements. Firstly, we need to check either the list is empty or not. The condition front == NULL becomes true if the list is empty, in this case , we simply write underflow on the console and make exit.

Operation on Linked Queue

• Otherwise, we will delete the element that is pointed by the pointer front. For this purpose, copy the node pointed by the front pointer into the pointer ptr. Now, shift the front pointer, point to its next node and free the node pointed by the node pointer.

Representation of a Queue using array

• In queue, insertion and deletion happen at the opposite ends, so implementation is not as simple as stack.
• To implement a queue using array, create an array 'arr' of size 'n' and take two variables front and rear both of which will be initialized to 0 which means the queue is currently empty.

Representation of a Queue using array

• Element rear is the index upto which the elements are stored in the array and front is the index of the first element of the array.
• The implementation of queue operations are as follows:

Representation of a Queue using array

Representation of a Queue using array

• Enqueue: Addition of an element to the queue. Adding an element will be performed after checking whether the queue is full or not. If rear < n which indicates that the array is not full then store the element at arr[rear] and increment rear by 1 but if rear == n then it is said to be an Overflow condition as the array is full.

Representation of a Queue using array

• Dequeue: Removal of an element from the queue. An element can only be deleted when there is at least an element to delete i.e. rear > 0. Now, element at arr[front] can be deleted but all the remaining elements have to shifted to the left by one position in order for the dequeue operation to delete the second element from the left on another dequeue operation.

Representation of a Queue using array

• Front: Get the front element from the queue i.e. arr[front] if queue is not empty.
• Display: Print all element of the queue. If the queue is non-empty, traverse and print all the elements from index front to rear.

Circular Queue

​

​

• We will explain the concept of circular queues using an example.
• In this queue, front = 2 and rear = 9. Now, if you want to insert a new element, it cannot be done because the space is available only at the left of the queue.

Circular Queue

• If rear = MAX – 1, then OVERFLOW condition exists.
• This is the major drawback of an array queue. Even if space is available, no insertions can be done once rear is equal to MAX – 1.
• This leads to wastage of space. In order to overcome this problem, we use circular queues.

​

Circular Queue

• In a circular queue, the first index comes right after the last index.
• A circular queue is full, only when front=0 and rear = Max – 1.

Inserting an Element in a Circular Queue

• For insertion we check for three conditions which are as follows:
• If front=0 and rear= MAX – 1, then the circular queue is full.

​

Inserting an Element in a Circular Queue

• If rear != MAX – 1, then the rear will be incremented and value will be inserted.

​

​

• If front!=0 and rear=MAX -1, then it means that the queue is not full. So, insert the new element.

​

​

​

Deleting an Element in a Circular Queue

• To delete an element again we will check for following conditions:
• If front = -1, then it means there are no elements in the queue. So an underflow condition will be reported.

​

​

​

Deleting an Element in a Circular Queue

• If the queue is not empty and after returning the value on front, if front = rear, then it means now the queue has become empty and so front and rear are set to -1.

​

​

​

Deleting an Element in a Circular Queue

• If the queue is not empty and after returning the value on front, if front = MAX -1, then front is set to 0.

​

​

​

Priority Queue

• A priority queue is a queue in which each element is assigned a priority. The priority of elements is used to determine the order in which these elements will be processed.
• The general rule of processing elements of a priority queue can be given as:
• An element with higher priority is processed before an element with lower priority.
• Two elements with same priority are processed on a first come first served (FCFS) basis.

​

Priority Queue

• Priority queues are widely used in operating systems to execute the highest priority process first.
• In computer’s memory priority queues can be represented using arrays or linked lists.
• When a priority queue is implemented using a linked list, then every node of the list contains three parts: (1) the information or data part, (ii) the priority number of the element, (iii) and address of the next element.

Priority Queue

• If we are using a sorted linked list, then element having higher priority will precede the element with lower priority.

Applications of Linked List

• Implementation of stacks and queues,
• Dynamic memory allocation : We use linked list of free blocks.
• Maintaining directory of names.
• Performing arithmetic operations on long integers.
• Image viewer – Previous and next images are linked, hence can be accessed by next and previous button.

Applications of Linked List

• Previous and next page in web browser – We can access previous and next url searched in web browser by pressing back and next button since, they are linked as linked list.
• Music Player – Songs in music player are linked to previous and next song. you can play songs either from starting or ending of the list.

Applications of Doubly Linked List

• Doubly Linked List is also used in constructing MRU/LRU (Most/least recently used) cache.
• In many operating systems, the thread scheduler (the thing that chooses what process needs to run at which time) maintains a doubly-linked list of all processes running at that time.

Applications of Circular Linked Lists

• We don’t need to maintain two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted node and front can always be obtained as next of last.

Applications of Circular Linked Lists

• Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, the operating system put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.

ANY DOUBTS?