Unit-III

LINKED LISTS
 Linked List
• A Linked list or one-way list is a linear
collection of data elements called nodes.
• The linear order is given by pointers.
• Each node is divided into two parts:
– First part is the info part
• contains the information of the element
– Second part is the link field or next pointer field
• contains the address of next node in the list.
Linked List with 6 nodes
 List pointer variable
• Linked list contain a list pointer variable called
START or NAME which contains the address of
first node in the list.
• If list is null or empty, START will contain Null
pointer.
Example
Representation of Linked List in memory
 Traversing a linked list
• Linked list is traversed in order to process each node at least
once.
• A pointer variable PTR points to the node which is currently
being processed.
• LINK[PTR] points to the next node to be processed.
• To move pointer to the next node in the list, following
assignment can be done:
PTR:=LINK[PTR]
Algorithm to traverse a linked list
(Traversing a linked list) Let LIST be a linked list in memory.
This algorithm traverses LIST, applying an operation PROCESS
to each element of LIST. The variable PTR points to the node
currently being processed.
Algorithm to find the number of elements in
the list
 Searching a linked list
If List is Unsorted
– An ITEM can be searched by traversing each
element of the list one by one using pointer
variable.
• ITEM is compared to INFO[PTR] of each node.
• Then the PTR is incremented.
Searching when List is Unsorted
 List is Sorted
• An ITEM can be searched by traversing each
element of the list one by one using pointer
variable.
– ITEM is compared to INFO[PTR] of each node.
– Then the PTR is incremented.
– If the ITEM exceeds INFO[PTR], we can stop
searching.
Algorithm
 Complexity of searching a sorted list
• Complexity is same as linear search algorithm
• i.e. O(n)

• Binary search algorithm cannot be applied to

search a sorted list as there is no way of
indexing the middle element in the list.
Memory Allocation/ Garbage Collection
• If a node is deleted from the list or the entire
list is deleted in a program, it becomes
reusable.
• To use this, reinsert this into the free storage
list.
– It can be done while using arrays.

• Alternatively, Garbage Collection can be done

to add the deleted space into free storage list.
 Garbage Collection
• It is done by the operating system periodically.

• It is done in two steps:

– Firstly,
• The computer runs through all lists
• Tags those cells which are currently in use.
– Secondly,
• the computer runs through memory
• Collects all the untagged space into the free storage list.

• Garbage collection takes place when,

– there is minimum amount of space left in free storage list.
– When the CPU is idle and has time to do the collection.
 Insertion into a Linked List
• Let LIST be a Linked List with successive nodes A and B.
• Node N is to be inserted into the list between nodes A
and B.
• After Insertion,
– node A points to new node N
– node N points to node B

• There can be two special cases of Insertion

– If new node N is the first node in the list
• START will point to N
– If new node N is the last node in the list
• N will contain the null pointer

• New node will be taken from AVAIL list which is

the free storage list in memory.
Data List and Free Storage List
Insertion at the beginning of the list
 Insertion after a given node
INSLOC (INFO, LINK, START, AVAIL, LOC, ITEM)
This algorithm inserts ITEM follows the node with location LOC or
inserts ITEM as the first node when LOC=NULL.
Insertion into a Sorted Linked List
Algorithm to find the location to insert
Algorithm to Insert
 Deletion from a linked list
• Let LIST be a linked list with a node N between nodes A and B.
• Node N is to be deleted from the link list.
• When deletion occurs, nextpointer field of node A now points to node B.
• Linked list is maintained in the memory as:
LIST (INFO, LINK, START, AVAIL)

• When node N is deleted, it is immediately returned to the AVAIL list.

 Free Storage (AVAIL) List
• While deleting a node and returning the memory to the AVAIL list, following
three pointer fields are changed:

– The nextpointer field of node A now points to node B, where node N previously
pointed.

– Nextpointer field of N now points to the original first node in the free pool, where
AVAIL previously pointed.

– AVAIL now points to the deleted node N.

Deleting the node following a given node
• We are given a location LOC of a node in LIST.
• We are also given the location LOCP of the
node preceding N.

• If N is the first node, LOCP=NULL.

 Deletion Algorithm
DEL (INFO, LINK, START, AVAIL, LOC, LOCP)
This algorithm deletes the node N with location LOC. LOCP is the
location of the node which precedes N or, when N is the first node,
LOCP=NULL.
Deleting a node with given ITEM of
information
 Header Linked List
• A header linked list is a linked list which always contains a special
node, called header node, at the beginning of the list.

• There are two kinds of header lists:

– A grounded header list:
• the last node contains the null pointer.

– A circular header list

• the last node points back to the header node.
Traversing a circular header list
Inserting an element in a circular header list
Deleting an element from a circular header
list
 Two-way Lists
• A two-way list is a linear collection of data elements, called
nodes.
• It is also called Doubly Linked List.
• Each node is divided into three parts:
– INFO
• Information field which contains the data of N
– FORW
• Pointer field which contains the location of next node in the list.
– BACK
• Pointer field which contains the location of preceding node in the list.
Example
Two-way Header Lists
 Operation on Two-Way Lists
• Traversing
• Searching
• Insertion
• Deletion
Inserting an element in Two-way header list
 Algorithm: Insertion
INSTWL (INFO, FORW, BACK, START, AVAIL, LOCA, LOCB, ITEM)
1. [OVERFLOW?] If AVAIL=NULL, then: Write: OVERFLOW, and Exit.
2. [Remove node from AVAIL list and copy new data into node.]
Set NEW:=AVAIL
AVAIL:=FORW[AVAIL],
INFO[NEW]:=ITEM
3. [Insert node into list.]
Set FORW[LOCA]:=NEW,
FORW[NEW]:=LOCB
BACK[LOCB]:=NEW
BACK[NEW]:=LOCA.
4. Exit.
Deleting an element from Two-way header
list
 Linked Representation of Stack
• Linked representation of stacks termed as
Linked Stack is implemented using singly
linked list.
• A node in the linked stack has two parts:
– INFO
• holds the element of the stack
– LINK
• holds pointer to the neighboring element in the stack.
Linked Representation of Stack
Stack Operations
PUSH Operation
POP Operation
Linked Representation of Queue
Queue Operations
Insert Operation
Delete Operation
 Dynamic Memory Allocation
• Dynamic memory allocation is defined as a
procedure in which size of the data structure is
changed during run-time.
• There are various library functions to facilitate
dynamic memory allocation.
– malloc()
– calloc()
– free()
• <stdlib.h> can be used in C programming to support
these functions.
 malloc()
• Dynamically allocates a single large block of
memory with specified size.
• Returns a pointer of type void.

• Syntax:
ptr = (cast-type*) malloc (byte-size)
• e.g.
ptr = (int*) malloc (5*sizeof(int));

• ptr holds the address of first byte in memory.

 calloc()
• calloc stands for contiguous allocation
• used to dynamically allocate the specified number of
blocks of memory of specified type.
• Initializes each block with default value 0.

• Syntax:
ptr = (cast-type*) calloc (n, element-size)
• e.g.
ptr = (float*) calloc (20, sizeof(float));

• Allocates contiguous space in memory for 25 elements

each with the size of float.
 free()

• Memory allocated using function malloc() and

calloc() cannot be de-allocated on their own.

• free() method is used to de-allocate the

memory.
• It helps to reduce the wastage of memory by
freeing it.
 Dynamic Implementation (Program)
• Dynamic Stack & Queue.docx