Hindustan Institute of Management and Computer Studies

Data Structures & Analysis of Algorithms (BMC205)

Unit -1
LINKED LIST

Self-Referential Structure
One or more of structure’s components is a pointer to the itself type.
struct node {
int data;
struct node *nextPtr;
}

Linked List
A linked list is a collection of “nodes” connected together via links. These nodes consist of
the data to be stored and a pointer to the address of the next node within the linked list. In the
case of arrays, the size is limited to the definition, but in linked lists, there is no defined size.
A linked list is a linear data structure, in which the elements are not stored at contiguous
memory locations.
There are following types of linked lists −
• Singly Linked List − It 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. The node
contains a pointer to the next node means that the node stores the address of the next
node in the sequence. A single linked list or a one-way list allows the traversal of

data only in one way.

• Doubly Linked List − The node point to the addresses of both previous and next
nodes. A doubly linked list or a two-way linked list is a more complex type of linked
list that contains a pointer to the next as well as the previous node in
sequence. Therefore, it contains three parts i.e. data, a pointer to the next node, and a
pointer to the previous node. This would enable us to traverse the list in the
backward direction as well.

• Circular Linked List − It can either be singly linked or doubly linked.

The last node in the Singly Circular linked list will point to the first node in the list.
 A Doubly Circular linked list or a circular two-way linked list is a more complex
type of linked list that contains a pointer to the next as well as the previous node in
the sequence. The difference between the doubly linked and circular doubly list is
the same as that between a singly linked list and a circular s i n g l y linked list. The
circular doubly linked list does not contain null in the previous field of the
first node.

• Header Linked List − Header node is not the actual node of the list. A header linked
list is a type of linked list that has a header node at the beginning of the list. In a
header linked list, HEAD points to the header node instead of the first node of the list.
The header node does not represent an item in the linked list. This data part of this
node is generally used to hold any global information (as count) about the entire
linked list. The next part of the header node points to the first node in the list.

A header linked list can be divided into two types:

• Grounded header linked list that stores NULL in the last node’s next field.
• Circular header linked list that stores the address of the header node in the next
part of the last node of the list.

Basic Operations with Linked List

1. Insertion - Insert an element to the list
i) At Beginning
ii) At End
iii) At a particular position
iv) Before or after a node on the basis of ‘Information’ part
2. Deletion - Delete an element from the list
i) At Beginning
ii) At End
iii) At a particular position
iv) Before or after a node on the basis of ‘Information’ part
3. Traverse - Displays the comp ete list
4. Search - on the basis of ‘Information’ part
5. Sort - on the basis of ‘Information’ part
6. Count
Advantages of Linked Lists:
• The size of the arrays is fixed: So we must know the upper limit on the number of
elements in advance. Also, generally, the allocated memory is equal to the upper limit
irrespective of usage, and in practical uses, the upper limit is rarely reached.
• Inserting a new element in an array of elements is expensive because a room has to be
created for the new elements and to create a room existing elements have to be shifted.

Disadvantages of Linked Lists:

• Random access is not allowed. We have to access elements sequentially starting from
the first node. So we cannot do a binary search efficiently with linked lists.
• Extra memory space for a pointer is required for each element of the list.
• Arrays have a better cache locality that can make a pretty big difference in performance.
• It takes a lot of time in traversing and changing the pointers.
• It will be confusing when we work with pointers.

Differences between array and linked-list

APPLICATIONS OF LINKED LISTS

• To implement other data structures such as stacks, queues, trees, and graphs.
• To maintain a directory of names.
• To perform arithmetic operations on long integers.
• To manipulate polynomials.
• To represent sparse matrices.

Polynomial is a mathematical expression that consists of variables and coefficients.

In the Polynomial linked list, the coefficients and exponents of the polynomial are defined
as the data node of the list. In a linked list node, contains 3 members, coefficient value,
exponent value and link to the next node.
A linked list that is used to store Polynomial looks like –
Polynomial: 3x3- 4x2 + 2x - 9
Linked List:

Example,
Input:
P1 = 5x2 + 4x1 + 2x0
P2 = 5x1 + 5x0
Output:
5x2 + 9x1 + 7x0

struct Node{
int coeff;
int pow;
struct Node *next;
};

Explanation − For adding two polynomials that are represented by a linked list, we check
values at the exponent value of the node. For the same values of exponent, we will add the
coefficients. Then return the final polynomial.

Algorithm
Input − polynomial p1 and p2 represented as a linked list.
Step 1: loop around all values of linked list and follow step 2 & 3.
Step 2: if the value of a node’s exponent is greater, copy this node to result node and head
towards the next node.
Step 3: if the values of both node’s exponent is same, add the coefficients and then copy the
added value with node to the result.
Step 4: Print the resultant node.

Garbage Collection:-
The operating system of a computer may periodically collect all the deleted space
onto the free-storage list. Any technique which does this collection is called garbage
collection. Garbage collection usually lakes place in two steps. First the computer runs
through all lists, tagging those cells which are currently in use, and then the computer runs
through the memory, collecting all untagged space onto the free-storage list. The garbage
collection may take place when there is only some minimum amount of space or no space at
all left in the free-storage list, or when the CPU is idle and has time to do the collection.
Generally speaking, the garbage collection is invisible to the programmer.

Overflow and Underflow:-

Sometimes new data are to be inserted 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
programmer may handle overflow by printing the message OVERFLOW. Observe that
overflow will occur with our linked lists when AVAIL = NULL and there is an insertion.
Analogously, the term underflow refers to the situation where one wants to delete data
from a data structure that is empty. The programmer may handle underflow by printing the
message UNDERFLOW. Observe that underflow will occur with our linked lists when
START = NULL and there is a deletion.

Stack: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle,
i.e., the item which is added at last is removed first. The best analogy for a stack is either a
pile of coins or a pile of books kept one above the other. You can add or remove an item from
the top only. It can be implemented using an array and linked list.

Operations on Linked Stack: Following operations can be performed on a stack.

• push(): It inserts an element to the top of the stack.
• pop(): It removes an element from the top of the stack.
• peek(): It returns the top element of the stack.
• size(): It returns the size of the stack, i.e., the total number of items in a stack.
• isEmpty(): Returns a boolean value. It returns true if the stack is empty. Else, it
returns false.
• isFull(): Returns a boolean value. It returns true if the stack is full. Else, it
 returns false.

A stack is represented using nodes of a linked list. Each node consists of two parts: data and
next (storing the address of the next node). The data part of each node contains the assigned
value, and the next points to the node containing the next item in the stack. The top refers to
the topmost node in the stack. Both the push() and pop() operations are carried out at the
front/top of the linked list.

Steps for implementing stack using linked list:

1. Push Function: Adding or inserting a new element to a stack is known as the Push() operation in
the stack. Elements can only be pushed at the top of the stack.
• Create a new node using dynamic memory allocation and assign value to the node.
• Check if stack is empty or not, i.e, (top == NULL).
• If it is empty, then set the next pointer of the node to NULL.
• If it is not empty, the newly created node should be linked to the current top element of the
stack, i.e.,
• Make sure that the top of the stack should always be pointing to the newly created node.

2. Pop Function: Removing or deleting an element from a stack is known as the Pop()
operation in the stack. Elements are popped from the top of the stack. There should be at least one
element in the stack to perform the pop() operation.
• Check if stack is empty or not, i.e, (TOP == NULL).
• If it is not empty, then create a temporary node and set it to top. Now, create another
variable and copy the data of top element to this variable.
• Now, make top point to the next node.
• Delete the temporary node.
• If it is empty, then print Stack Underflow.

3. Display Function: It is used to display the content of the stack.

• Check if stack contains at least one element or not.
• If the stack is empty print “No elements in the stack.”
• Else, define a node pointer and initialize it with the top.
• Display data of node pointer until the next node pointer becomes NULL.

Queue: A queue is a linear data structure that follows the First In, First Out (FIFO) principle,
which means that the element which is inserted first in the queue will be the first one to be
removed from the queue. A good example of a queue is a queue of customers purchasing a
train ticket, where the customer who comes first will be served first. It can be implemented
using an array and linked list.

Operation on Linked Queue: Each node of a linked queue consists of two fields: data and
next (storing address of next node). The data field of each node contains the assigned value,
and the next points to the node containing the next item in the queue.

A linked queue consists of two pointers, i.e., the front pointer and the rear pointer. The front
pointer stores the address of the first element of the queue, and the rear pointer stores the
 address of the last element of the queue.
Queue support operations like enqueue (insertion) and dequeue (deletion). Insertion is
performed at the rear end, whereas deletion is performed at the front end of the queue. If front
and rear both points to NULL, it signifies that the queue is empty.

Steps for implementing queue using linked list:

1. Enqueue Function: It adds an element to the end of the queue. The last element can be tracked
using the rear pointer.
• First, build a new node with given data.
• Check if the queue is empty or not.
• If a queue is empty then, a new node is assigned to the front and rear.
• Else make next of rear as new node and rear as a new node.

2. Dequeue Function: It always removes the first element of the queue. For dequeue, the queue
must contain at least one element, else underflow conditions will occur.
• Check if queue is empty or not.
• If the queue is empty, then dequeue is not possible.
• Else store front in temp
• And make next of front as the front.
• Delete temp, i.e, free(temp).

3. Display Function: It is used to display the content of the queue.

• Check if queue contains at least one element or not.
• If the queue is empty print “No elements in the queue.”
• Else, define a node pointer and initialize it with the front.
• Display data of node pointer until the next node pointer becomes NULL.
---------------------------------------------------------------------------------