UNIT-3

SYLLABUS
Lists

• Concepts of Link List and their representation;

Two way lists; Circular link list; Basic operations &
their algorithms: Transverse, Insert, Delete,
Searching and Sorting of data in List; Storage
Allocation & Garbage Collection; Linked stack and
queues; Generalized List; sparse matrix
representation using generalized list structure.
 Linked List
• Linked List is a linear data structure, in which
elements are not stored at a contiguous
location, rather they are linked using pointers.
Linked List forms a series of connected nodes,
where each node stores the data and the
address of the next node.
 Link List
• Linked list is a linear data structure that includes a
series of connected nodes.
• Linked list can be defined as the nodes that are
randomly stored in the memory.
• A node in the linked list contains two parts, i.e., first is
the data part and second is the address part.
• The last node of the list contains a pointer to the null.
• If arrays accommodate similar types of data types,
linked lists consist of elements with different data
types that are also arranged sequentially.
Node Structure: A node in a linked list typically consists of two components:
Data: It holds the actual value or data associated with the node.
Next Pointer: It stores the memory address (reference) of the next node in
the sequence.
Head and Tail: The linked list is accessed through the head node, which points
to the first node in the list. The last node in the list points to NULL or nullptr,
indicating the end of the list. This node is known as the tail node
 Representation of a Linked list

• Linked list can be represented as the connection

of nodes in which each node points to the next
node of the list.
• 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. Any amount of data can be stored in it and
can be deleted from it.
 Why linked list data structure needed?

• Dynamic Data structure: The size of memory can be

allocated or de-allocated at run time based on the
operation insertion or deletion.
• Ease of Insertion/Deletion: The insertion and deletion of
elements are simpler than arrays since no elements need to
be shifted after insertion and deletion, Just the address
needed to be updated.
• Efficient Memory Utilization: As we know Linked List is a
dynamic data structure the size increases or decreases as
per the requirement so this avoids the wastage of memory.
• Implementation: Various advanced data structures can be
implemented using a linked list like a stack, queue, graph,
hash maps, etc.
 Why use linked list over array?

• Linked list is a data structure that overcomes the

limitations of arrays. Let's first see some of the
limitations of arrays -
• The size of the array must be known in advance before
using it in the program.
• Increasing the size of the array is a time taking process.
It is almost impossible to expand the size of the array
at run time.
• All the elements in the array need to be contiguously
stored in the memory. Inserting an element in the array
needs shifting of all its predecessors.
 Disadvantages of Linked list

• The limitations of using the Linked list are given as follows -

• Memory usage - In linked list, node occupies more memory than
array. Each node of the linked list occupies two types of variables,
i.e., one is a simple variable, and another one is the pointer
variable.
• Traversal - Traversal is not easy in the linked list. If we have to
access an element in the linked list, we cannot access it randomly,
while in case of array we can randomly access it by index. For
example, if we want to access the 3rd node, then we need to
traverse all the nodes before it. So, the time required to access a
particular node is large.
• Reverse traversing - Backtracking or reverse traversing is difficult in
a linked list. In a doubly-linked list, it is easier but requires more
memory to store the back pointer.
 Applications of Linked list

• The applications of the Linked list are given as follows -

• With the help of a linked list, the polynomials can be represented as well as we can
perform the operations on the polynomial.
• A linked list can be used to represent the sparse matrix.
• The various operations like student's details, employee's details, or product details
can be implemented using the linked list as the linked list uses the structure data
type that can hold different data types.
• Using linked list, we can implement stack, queue, tree, and other various data
structures.
• The graph is a collection of edges and vertices, and the graph can be represented
as an adjacency matrix and adjacency list. If we want to represent the graph as an
adjacency matrix, then it can be implemented as an array. If we want to represent
the graph as an adjacency list, then it can be implemented as a linked list.
• A linked list can be used to implement dynamic memory allocation. The dynamic
memory allocation is the memory allocation done at the run-time.
 Operations performed on Linked list

• The basic operations that are supported by a list

are mentioned as follows -
• Insertion - This operation is performed to add an
element into the list.
• Deletion - It is performed to delete an operation
from the list.
• Display - It is performed to display the elements
of the list.
• Search - It is performed to search an element
from the list using the given key.
 Insertion Operation

• Given a Linked List, the task is to insert a new

node in this given Linked List at the following
positions:
• At the front of the linked list
• After a given node.
• At the end of the linked list.
How to Insert a Node at the Front/Beginning of
Linked List
How to Insert a Node after a Given Node in
Linked List
How to Insert a Node at the End of Linked List
 Delete from a Linked List:-

You can delete an element in a list from:

• Beginning
• End
• Middle
Delete from a Linked List:-
 Traverse a Linked List

• Displaying the contents of a linked list is very simple. We keep

moving the temp node to the next one and display its contents.
• When temp is NULL, we know that we have reached the end of the
linked list so we get out of the while loop.
 Sort Elements of a Linked List

• We will use a simple sorting algorithm, Bubble Sort, to

sort the elements of a linked list in ascending order
below.
• Make the head as the current node and create another
node index for later use.
• If head is null, return.
• Else, run a loop till the last node (i.e. NULL).
• In each iteration, follow the following step 5-6.
• Store the next node of current in index.
• Check if the data of the current node is greater than
the next node. If it is greater, swap current and index.
 Search an Element on a Linked List

• You can search an element on a linked list using a

loop using the following steps. We are
finding item on a linked list.
• Make head as the current node.
• Run a loop until the current node
is NULL because the last element points to NULL.
• In each iteration, check if the key of the node is
equal to item. If it the key matches the item,
return true otherwise return false.
Search an Element on a Linked List
 Types of linked lists:

• There are mainly three types of linked lists:

• Single-linked list
• Double linked list
• Circular linked list
 Single-linked list:

• In a singly linked list, each node contains a reference to

the next node in the sequence. Traversing a singly
linked list is done in a forward direction.
 Double-linked list:
• In a doubly linked list, each node contains references to both the next and
previous nodes. This allows for traversal in both forward and backward directions,
but it requires additional memory for the backward reference.
• 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.

https://www.geeksforgeeks.org/types-of-linked-list/
 Circular linked list:

• In a circular linked list, the last node points back

to the head node, creating a circular structure. It
can be either singly or doubly linked.
 Storage Allocation & Garbage Collection

GARBAGE COLLECTION
• Together with a link list in memory a special list is maintain which consist
of unused memory size. This list which has its own pointer is called the list
of available space or the free storage list or the free pool. The OS of a
computer may periodically collect all the deleted space on to the free
storage list .Any technique which does this collection is called Garbage
collection.
• Garbage collection usually takes 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 of onto the free storage list. The garbage collection may takes place
when there is only some amount of space or free storage list when the
CPU is idle or no and has time to do the collection.
• NEW AND DELETE
• https://www.javatpoint.com/garbage-collection-in-data-structure
 Garbage Collection
• Garbage collection (GC) is a dynamic technique for memory management and heap
allocation that examines and identifies dead memory blocks before reallocating storage for
reuse.
• Garbage collection's primary goal is to reduce memory leaks. Garbage collection frees the
programmer from having to deallocate and return objects to the memory system manually.
• Garbage collection can account for a considerable amount of a program's total processing
time, and as a result, can have a significant impact on performance. Stack allocation, region
inference, memory ownership, and combinations of various techniques are examples of
related techniques.
• The basic principles of garbage collection are finding data objects in a program that cannot be
accessed in the future and reclaiming the resources used by those objects.
• Garbage collection does not often handle resources other than memory, such as network
sockets, database handles, user interaction windows, files, and device descriptors. Methods
for managing such resources, especially destructors, may be sufficient to manage memory
without the requirement for GC.
• Other resources can be associated with a memory sector in some GC systems, which, when
collected, causes the task of reclaiming these resources.
Linked stack
Linked stack
Linked stack
Linked queues
 Linked queues
• 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.
• 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.
 Generalized List
• A Generalized Linked List L, is defined as a
finite sequence of n>=0 elements, l1, l2, l3, l4,
…, ln, such that li are either item or the list of
items. Thus L = (l1, l2, l3, l4, …, ln) where n is
total number of nodes in the list.
• To represent a list of items there are certain assumptions about the node
structure.
• Flag = 1 implies that down pointer exists
• Flag = 0 implies that next pointer exists
• Data means the item.
• Down pointer is the address of node which is down of the current node
• Next pointer is the address of node which is attached as the next node
Example of GLL {List representation}
( a, (b, c), d)

When first field is 0, it indicates that the second field is variable. If first field is 1
means the second field is a down pointer, means some list is starting.

https://www.geeksforgeeks.org/generalized-linked-list/
Example
 Why Generalized Linked List?
• Generalized linked lists are used because
although the efficiency of polynomial
operations using linked list is good but still,
the disadvantage is that the linked list is
unable to use multiple variable polynomial
equation efficiently. It helps us to represent
multi-variable polynomial along with the list
of elements.
 Sparse Matrix
• A matrix is a two-dimensional data object made of m
rows and n columns, therefore having total m x n
values. If most of the elements of the matrix have 0
value, then it is called a sparse matrix.
• Why to use Sparse Matrix instead of simple matrix ?
• Storage: There are lesser non-zero elements than zeros
and thus lesser memory can be used to store only
those elements.
• Computing time: Computing time can be saved by
logically designing a data structure traversing only non-
zero elements..
• Representing a sparse matrix by a 2D array leads to wastage of lots
of memory as zeroes in the matrix are of no use in most of the
cases.
• So, instead of storing zeroes with non-zero elements, we only store
non-zero elements. This means storing non-zero elements
with triples- (Row, Column, value).
 Sparse Matrix and its representations

Sparse Matrix can be represented Using-

• Arrays
• Linked Lists
• List of Lists (LIL)
 Method 1: Using Arrays:

• 2D array is used to represent a sparse matrix

in which there are three rows named as
• Row: Index of row, where non-zero element is
located
• Column: Index of column, where non-zero
element is located
• Value: Value of the non zero element located
at index – (row,column)
Method 1: Using Arrays:
 Method 2: Using Linked Lists
•
In linked list, each node has four fields. These
four fields are defined as:
• Row: Index of row, where non-zero element is
located
• Column: Index of column, where non-zero
element is located
• Value: Value of the non zero element located at
index – (row,column)
• Next node: Address of the next node
Method 2: Using Linked Lists
 Method 3 -List of Lists (LIL)

• One of the possible representation of sparse

matrix is List of Lists (LIL). Where one list is
used to represent the rows and each row
contains the list of triples: Column index,
Value(non – zero element) and address
field, for non – zero elements. For the best
performance both lists should be stored in
order of ascending keys.
List of Lists (LIL)
 Method 4-Dictionary of Keys

• An alternative representation of sparse matrix

is Dictionary. For the key field of the
dictionary, pair of row and column index is
used that maps with the non – zero element
of the matrix. This method saves space but
sequential access of items is costly.
In C++, dictionary is defined as map class of
STL(Standard Template Library).