MODULE 3
Linked List: Definition, Array Vs Linked List, Dynamic memory management.
Representation of a Linked List, Classification (Singly Linked List, Doubly Linked List,
Circular singly linked list), Operations on Singly Linked List- Traversal, Insertion, Deletion
and Searching.
Applications of Linked List: Polynomial representation and manipulation (Addition only).
Operations on Doubly Linked List- Traversal, Insertion, Deletion and Searching, Circular
Linked List (Concept only) Linked List representation of Stack and Queue, Stack
implementation and Operations on Stack using Linked List, Queue implementation and
Operations on Queue using Linked list.
LINKED LIST
● Linked list is called dynamic data structure where amount of memory required can be
varied during its use.
● In linked list, adjacency between the elements are maintained by means of links or
pointers
● A link or pointer actually is the address (memory location) of the subsequent element.
● Thus, in a linked list, data (actual content) and link (to point to the next data) both are
required to be maintained.
● An element in a linked list is specially termed as node.
● A node consists of two fields: DATA (to store the actual information) and LINK (to
point to the next node).
DEFINITION
● A linked list is an ordered collection of finite, homogeneous data elements called
nodes where the linear order is maintained by means of links or pointers.
● Depending on the requirements the pointers are maintained.
● Linked list can be classified into three major groups:
○ Single Linked List
○ Circular Linked List
○ Double Linked List
ARRAY Vs LINKEDLIST
[Link]. Array Linked List
An array is a consistent set of fixed A linked list is an ordered set of a
1.
number of data items. variable number of data items.
They are stored in contiguous memory They are not stored in contiguous
2.
locations. memory locations.
In the case of arrays, the memory In the liked lists, memory allocation is
3.
allocation is done at compile time. done at run time.
4. Arrays are fixed in size. Linked lists are dynamic in size.
Arrays require less memory space as Linked lists require more memory
5.
compared to linked lists. space.
In the case of arrays, the insertion and In the linked lists, the insertion and
6. deletion operations require more time to deletion operations take less time.
execute.
In arrays, accessing the elements is In linked lists, the whole linked list is
7. easier. to be traversed to access the elements.
DYNAMIC MEMORY MANAGEMENT.
Memory Allocation Process:
● Global variables, static variables and program instructions get their memory in
permanent storage area whereas local variables are stored in a memory area called
Stack.
● The memory space between these two region is known as Heap area. This region is
used for dynamic memory allocation during execution of the program. The size of
heap keep changing.
● The process of allocating memory at runtime is known as dynamic memory
allocation. Library routines known as memory management functions are used for
allocating and freeing memory during execution of a program.
● There are 4 library functions provided by C defined under <stdlib.h> header
file to facilitate dynamic memory allocation in C programming. They are:
1. malloc()
2. calloc()
3. free()
4. realloc()
malloc() function:
● malloc() function is used for allocating block of memory at runtime. This
function reserves a block of memory of the given size and returns a pointer of
type void. This means that we can assign it to any type of pointer using
typecasting.
Syntax:
void* malloc(byte-size)
Eg:
int *x;
x = (int*)malloc(50*sizeof(int)); //memory space allocated to variable x
free(x);
calloc() function:
● calloc() is another memory allocation function that is used for allocating
memory at runtime. calloc function is normally used for allocating memory to
derived data types such as arrays and structures.
Syntax:
void *calloc(number of items, element-size)
Eg:
{
struct employee
char *name;
int salary;
};
typedef struct employee emp;
emp *e1;
e1 = (emp*)calloc(30,sizeof(emp));
realloc() function:
● realloc() changes memory size that is already allocated dynamically to a
variable.
Syntax:
void* realloc(pointer, new-size)
Eg:
int *x;
x = (int*)malloc(50 * sizeof(int));
x = (int*)realloc(x,100); //allocated a new memory to variable x
free() function:
● The free( ) function is used to de-allocate the previously allocated memory
using malloc( ) or calloc( ) functions.
Syntax :
free (ptr_var);
REPRESENTATION OF A LINKED LIST
● There are two ways to represent a linked list in memory:
1. Static representation using array
2. Dynamic representation using free pool of storage
STATIC REPRESENTATION
● In static representation of a single linked list, two arrays are maintained: one array for
data and the other for links.
● Two parallel arrays of equal size are allocated which should be sufficient to store the
entire linked list.
DYNAMIC REPRESENTATION
● The efficient way of representing a linked list is using the free pool of storage.
● In this method, there is a memory bank (which is nothing but a collection of free
memory spaces) and a memory manager (a program, in fact).
● During the creation of a linked list, whenever a node is required the request is placed
to the memory manager; the memory manager will then search the memory bank for
the block requested and, if found, grants the desired block to the caller.
● Again, there is also another program called the garbage collector; it plays whenever a
node is no more in use; it returns the unused node to the memory bank.
● It may be noted that memory bank is basically a list of memory spaces which is
available to a programmer.
● Such a memory management is known as dynamic memory management. The
dynamic representation of linked list uses the dynamic memory management policy.
● The mechanism of dynamic representation of single linked list is illustrated in above
figures.
● A list of available memory spaces is there whose pointer is stored in AVAIL. For a
request of a node, the list AVAIL is searched for the block of right size.
● If AVAIL is null or if the block of desired size is not found, the memory manager will
return a message accordingly.
● Suppose the block is found and let it be XY. Then the memory manager will return the
pointer of XY to the caller in a temporary buffer, say NEW.
● The newly availed node XY then can be inserted at any position in the linked list by
changing the pointers of the concerned nodes.
● In first figure, the node XY is inserted at the end and change of pointers is shown by
the dotted arrows. Second f
● igure explains the mechanism of how a node can be returned from a linked list to the
memory bank.
SINGLE LINKED LIST
❖ In a single linked list each node contains only one link which points the subsequent
node in the list.
● Here, N1, N2, .., No are the constituent nodes in the list.
● HEADER is an empty node (having data content NULL) and only used to store a
pointer to the first node N1.
● Thus, if one knows the address of the HEADER node from the link field of this node,
next node can be traced and so on.
● This means that starting from the first node one can reach to the last node whose link
field does not contain any address rather a null value.
DOUBLE LINKED LIST
● In a single linked list, every node has a link to its next node in the sequence. So, we
can traverse from one node to another node only in one direction and we can not
traverse back.
● In a double linked list, every node has a link to its previous node and next node.
● So, we can traverse forward by using the next field and can traverse backward by
using the previous field.
● Every node in a double linked list contains three fields and they are shown in the
following figure
● In double linked list, the first node must be always pointed by head.
○ Always the previous field of the first node must be NULL.
○ Always the next field of the last node must be NULL.
CIRCULAR SINGLY LINKED LIST
● In a circular Singly linked list, the last node of the list contains a pointer to the first
node of the list.
● We can have circular singly linked list as well as circular doubly linked list.
● We traverse a circular singly linked list until we reach the same node where we
started.
● The circular singly liked list has no beginning and no ending.
● There is no null value present in the next part of any of the nodes.
● The following image shows a circular singly linked list.
● Circular linked list are mostly used in task maintenance in operating systems.
● There are many examples where circular linked list are being used in computer
science including browser surfing where a record of pages visited in the past by the
user, is maintained in the form of circular linked lists and can be accessed again on
clicking the previous button.
OPERATIONS ON SINGLY LINKED LIST
Possible operations on a single linked list are listed as below:
● Traversing a list
● Insertion of a node into a list
● Deletion o f a node from a list
● Copy a linked list to make a duplicate
● Merging two linked lists into a larger list
● Searching for an element in a list.
We will assume the following convention: say X is a node. The values in the DATA field and
LINK field will be denoted as [Link] and [Link] respectively. We will write NULL to
imply that value in the field like DATA, LINK is nil.
Traversing a single linked list
To traverse a single linked list we mean to visit every node in the list starting from the first
node to the last node. Following is the algorithm TRAVERSE_SL for the same.
Algorithm TRAVERSE_SL (HEADER)
Input: HEADER is the pointer to the header node.
Output: According to the PROCESS( )
Data structures: A single linked list whose address of the starting node is known from
HEADER
Insertion of a node into a single linked list
There are various positions where a node can be inserted:
(i) Insert at front (as a first element)
(ii) Insert at end (as a last element)
(iii) Insert at any position.
Assume a procedure GETNODE(NODE) to get a pointer of a memory block which suits the
type NODE. The procedure may be defined as below:
(i) Insert at front (as a first element)
(ii) Insert at end (as a last element)
The algorithm INSERT_SL_END is to insert a node into a single linked list at the end of the
list.
(iii) Insert at any position.
Deletion of a node from a single linked list
Like insertions, there are also various cases of deletion:
(i) Deletion at the front of the list
(ii) Deletion at the end of the list
(iii) Deletion at any position in the list.
Let us consider the procedure for various cases of deletions. We will assume a procedure
namely, RETURNNODE(PTR) which returns a node having pointer PTR to the free pool of
storage. The procedure RETURNNODE(PTR) may be defined as follows:
(i) Deletion at the front of the list
The algorithm DELETE_SL_FRONT is to delete a node from a single linked list at the front
of the list.
(ii) Deletion at the end of the list
The algorithm DELETE_SL_END is to delete a node at the end from a single linked list.
(iii) Deletion at any position in the list.
The next algorithm DELETE_SL_ANY is to delete a node from any position in the single
linked list.
Searching for a n element in a single linked list
The algorithm SEARCH_SL() is given below to search an item in a single linked list.
APPLICATIONS OF LINKED LIST
Polynomial Representation and Manipulation
With a linked list representation, each term of a polynomial is stored as a node in a linked list.
Each node contains three elements:
1. The coefficient of the term.
2. The exponent of the term.
3. Address of the next node in the list.
Coefficient Exponent Address of the next node
Considering the same example as above, the polynomial can be written as
Here, each node holds the coefficient and exponent as a pair, and the pointer links to the
following term in sequence. Linked list representation works very well for sparse
polynomials as there is no need to store zero coefficients.
Polynomial Addition Using Array
Example:
OPERATIONS ON DOUBLY LINKED LIST
Traversal on Doubly Linked List Algorithm
PTR = RPTR // RPTR = Right pointer. Here as PTR = START, if we go from
back then we will use LPTR (Left pointer)
Insertion of a node from a doubly linked list
There are various positions where a node can be inserted:
(i) Insert at front (as a first element)
(ii) Insert at end (as a last element)
(iii) Insert at any position.
(i) Insert at front (as a first element)
(ii) Insert at end (as a last element)
(iii) Insert at any position.
Deletion of a node from a doubly linked list
Like insertions, there are also various cases of deletion:
(i) Deletion at the front of the list
(ii) Deletion at the end of the list
(iii) Deletion at any position in the list.
(i) Deletion at the front of the list
(ii) Deletion at the end of the list
(iii) Deletion at any position in the list.
Searching for an element in a doubly linked list
The algorithm SEARCH_DL() is given below to search an item in a doubly linked list.
Input: A doubly linked list with data and the element ELEMENT to be searched.
Output: Location of the node containing ELEMENT (if found), else "Not Found".
Data structure: Doubly linked list structure whose pointer to the header node is HEADER.
Steps:
1. ptr = HEADER
2. If ptr = NULL then
1. Print "List is empty"
2. Exit
3. While ptr != NULL do
1. If [Link] = ELEMENT then
1. Print "Element found"
2. Return pointer ptr (or its position)
2. Else
1. ptr = [Link]
4. EndWhile
5. Print "Element not found"
LINKED LIST REPRESENTATION OF STACK
● A single linked list structure is sufficient to represent any stack. Here, the DATA field
is for the ITEM, and the LINK field is, as usual, to point to the next item.
● The above figure depicts such a stack using a single linked list.
● In the linked list representation, the first node on the list is the current item that is the
item at the top of the stack and the last node is the node containing the bottom-most
item.
● Thus, a PUSH operation will add a new node in the front and a POP operation will
remove a node from the front of the list.
● The SIZE of the stack is not important here because this representation allows
dynamic stacks instead of static stacks, as with arrays.
● In the linked list representation of a stack, whether a stack is empty or not can be
found out by testing the LINK field of the STACK_HEAD node.
OPERATIONS ON STACKS
PUSH OPERATION:
POP OPERATION:
STATUS OPERATION:
LINKED LIST REPRESENTATION OF QUEUE
● Here, we select a double linked list which allows us to move both ways. Above figure
shows the double, linked list representation of a queue.
● The pointers FRONT and REAR point the first node and the last node in the list.
● Two states of the queue, either empty or containing some elements, can be judged by
the following tests:
● Queue is empty
○ FRONT = REAR = HEADER
○ HEADER→RLINK = NULL
● Queue contains at least one element
OPERATIONS ON QUEUE
The insertion and deletion operations are straightforward and the same as in the algorithm
InsertEnd_DL (for Enqueue) and algorithm DeleteFront_DL (for Dequeue).
ENQUEUE OPERATION:
DEQUEUE OPERATION:
Applications of Doubly Linked List (DLL)
1. Web Browser History – Moving forward and backward between visited pages.
2. Music/Video Playlists – Skip forward or backward to the previous/next song or
video.
Applications of Circular Linked List (CLL)
1. Round-Robin CPU Scheduling – Each process is given equal CPU time in rotation.
2. Multiplayer Board Games – Players take turns in a circular manner.
Applications of Singly Linked List (SLL)
1. Image Viewer / Slideshow – Moving from one image to the next.
2. Dynamic Memory Allocation (Free List Management) – Keeping track of free
memory blocks.