MODULE 3 - LINKED LIST AND MEMORY MANAGEMENT

Self Referential Structures, Dynamic Memory Allocation, Singly Linked List-Operations on

Linked List, Doubly Linked List, Circular Linked List, Stacks and Queues using Linked List,
Polynomial representation using Linked List, Memory allocation and de-allocation-First-fit,
Best-fit and Worst-fit allocation schemes

Disadvantage of using array

 Memory resizing is not possible. i.e. array size is fixed- it is a static data structure.
 Array requires continuous memory locations to store data.
 Wastage of memory

1. LINKED LIST

 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.
 A linked list is a dynamic data structure where the amount of memory required can be
varied during its use.
 In the linked list, the adjacency between the elements is maintained by means of links or
pointers.
 A link or pointer actually is the address (memory location) of the subsequent element.
 An element in a linked list is a specially termed node, which can be viewed as shown in the
figure.
 A node consists of two fields : DATA (to store the actual information) and LINK (to point
to the next node)

links to the next node

 A linked list is called "linked" because each node in the series has a pointer that points to the
next node in the list.
 Head: pointer to the first node
  The last node points to NULL

 Depending on the requirements the pointers are maintained, and accordingly the linked list
can be classified into three major groups:
1. Single linked list
2. Circular linked list
3. Double linked list.

SINGLE LINKED LIST

 In any single linked list, every "Node" contains two fields, data and link.
 The data field is used to store actual value of that node and link field is used to store the
address of the next node in the sequence.
 Each node contains only one link which points to the subsequent node in the list.
 The header node points to the 1st node in the list
 The link field of the last node contain NULL(ᶲ) value.
 Here one can move from left to right only. So it is also called one-way list

Representation of a linked list in memory

Two ways:
1. Static representation using array
2. Dynamic representation using free pool storage

1. Static representation
Two arrays are maintained:
– One for data and other for links.
2. Dynamic representation
 The efficient way of representing a linked list is using the free pool of storage.
 There is a
– memory bank : Collection of free memory spaces &
– memory manager: a program
 Whenever a node is required, the request is placed to the memory manager.
 It will search the memory bank for the block. If found, it will be granted.
 Garbage collector: Another program that returns the unused node to the memory bank.
  Returning a node to memory bank

Operations on a Single Linked List

 Traversing the list
 Inserting a node into the list
 Deleting a node from the list
 Merging the list with another to make a larger list
 Node creation
struct node
{
int data;
struct node *link;
};

 Function used for memory allocation is “malloc”

New_node = (struct node*)malloc (sizeof (struct node))

1. Traversing a single linked list

 Here we visit every node in the list starting from the first node to the last one.
Traverse()
1. Set ptr=head; //initialize the pointer ptr
2. While (ptr!=null) do
3. print ptr->data
4. ptr= ptr->link; //ptr now points to the next node

2. Inserting a node into the list

A. Inserting at the front ( as a first element)

B. Inserting at the end( as a last element)
C. Inserting at any other position

A. Inserting at the front

Algorithm: Insert a new node temp with data ‘item’

1. Create a pointer temp of type struct node

2. Create a new node temp using malloc function
temp = (struct node*) malloc(sizeof(struct node));
3. if (temp==NULL)
4. print “memory underflow, no insertion”
5. else
 6. temp->data= item
7. Set temp-> link=head
8. head=temp

B. Inserting at the end

 Here first we need to traverse the list to get the last node.

1. Create a pointer temp & ptr of type struct node

2. Create a new node temp using malloc function
temp = (struct node*) malloc(sizeof(struct node));
3. Set ptr=head; //initialize the pointer ptr
4. While (ptr->link!=null) do
5. ptr= ptr->link; //ptr now points to the next node
6. ptr->link= temp
7. temp->data=item

C. Insertion- At any position in the list

1. Create a pointer temp & ptr of type struct node

2. Create a new node temp using malloc function
temp = (struct node*) malloc(sizeof(struct node));
3. Read the value key of node after which a new node is to be placed
4. Set ptr=head
5. Repeat while (ptr-> data!=key) and (ptr->link!=NULL)
6. ptr=ptr-> link
7. If (ptr->link==NULL)
8. print “search fails”;
9. else
10. temp->link= ptr-> link
11. ptr->link= temp
3. Deleting a node from the list

 In a linked list, an element can be deleted:

A. From the 1st location
B. From the last location
C. From any position in the list

free(ptr) : It will free the location pointed by ptr

A. Deletion- From the beginning

1. Create a pointer ptr of type struct node

2. If (head==NULL) then exit
3. Else set ptr = head
4. set head=ptr-> link
5. free(ptr)

B. Deletion- From the end

1. Create a pointer ptr & temp of type struct node.
2. If (head -> link ==NULL) do step 3,4,5 else goto 6
3. ptr=head
4. head=NULL
5. free(ptr)
6. ptr=head
7. temp = head -> link
8. while(tem -> link !=NULL) do 9,10 else goto 11
9. ptr=temp
10. temp= tem -> link
11. ptr-> link =NULL
12. free (temp)

C. Deletion- From any position

 1. Read the value key that is to be deleted
2. Create pointer ptr & temp of type struct node
3. Set ptr=head
4. if head=NULL then print underflow and exit
5. temp=ptr
6. while(ptr!=null) do step 7,8,9
7. If(ptr->data=key) then
a) temp->link=ptr->link
b) free(ptr) & exit
8. temp=ptr
9. Ptr = ptr->link

4. Merging
 Two linked list L1 and L2.
 Merge L2 after L1
1. Set ptr= head1
2. While(ptr->link!= NULL) do step 3 else goto step 4
3. ptr=ptr->link
4. ptr->link=head2
5. Return(head2)
6. Head=head1
7. Stop

2. DOUBLY LINKED LIST

 Single linked list= one-way list

 List can be traversed in one direction only
 Double linked list= Two-way list
 List can be traversed in two directions
 two- way list is a linear collection of data elements called nodes where each node N is
divided in to three parts
– Data field contains the data of N
– LLINK field contains the pointer to the preceding Node in the list
– RLINK field contains the pointer to the next node in the list
iii) Insertion- after an element key
i) Deletion- from 1st location

ii) Deletion- from last location

iii) Deletion- from intermediate location
3. CIRCULAR LINKED LIST
 In a single linked list, the link field of the last node is null.
 If we utilize this link field to store the pointer of the header node, a number of advantages
can be gained.
 A linked list, whose last node points back to the first node, instead of containing the null
pointer is called a circular list

 Advantages:
 1. Accessibility of a member node – here every member node is accessible from any
node by merely chaining through the list
eg: Finding of earlier occurrence or post occurrence of a data will be easy
2. Null link problem- Null value in next field may create problem during the
execution of the program if proper care is not taken
3. Some easy-to-implement operations - Operations like merging, splitting, deletion,
dispose of an entire list etc can be done easily with circular list

 Disadvantages:
 If not cared, system may get trap into in infinite loop
 It occurs when we are unable to detect the end of the list while moving from one
node to the next
 Solution: Special node can be maintained with data part as NULL and this node
does not contain any valid information. So its just a wastage of memory space

Insertion in circular linklist

 We want to insert data ‘X’ after a given position, ‘pos’

 Here we are using a pointer called last, which points to the last node
1. Create a pointer temp and q of type struct node
2. Set q=last->link and i=1
3. While(i<pos) do step 4
4. q=q->link & increment I
5. Create a new node temp usin malloc function
temp = (struct node*) malloc(sizeof(struct node));
6. temp->link=q->link
7. temp->data = X
8. q->link = temp

Deletion in circular Linked List

1. if last = NULL print under flow and exit

// Linkedlist containing only one node
2. If last -> link = last & last -> data = key then do the steps 3,4,5
 3. temp= last
4. Last = NULL
5. free(temp)
6. q = last ->link
//Deleting first node
7. if q->data =key do 8,9,10
8. temp = q
9. Last->link= q->link
10. free(temp)
// deleting Middle node
11. Repeat steps 12 to 16 while q->link!=last
12. if q->link->data =key do step 13,14,15
13. temp = q->link
14. q->link= tem->link
15. Free(temp)
//Deleting last node
16. If q->link ->data = key
17. temp = q->link
18. q->link=last->link
19. Free(temp)
20. Last=q

4. STACKS USING LINKED LIST

 Stack can also be represented using a singly linked list.
 Linked lists have many advantages compared to arrays.
 In linked list, the DATA field contains the elements of stack and LINK field points to the
next element in the stack.
 Here Push operation is accomplished by inserting a new node in the front or start of the
list.
 Pop is done by removing the element from the front of the list
 he
ad n
ddd ccc bbb aaa ul
l
to
p
Insertion- At the beginning
Algorithm: PUSH()
1. Create a new node temp //struct node *temp = (struct node*) malloc(sizeof(struct node));
2. If (temp==NULL)
3. print “memory underflow, no insertion”
4. else
5. temp->data= item
6. temp-> link=head
7. head=temp
Deletion- From the beginning
Algorithm: POP()
1. Start
2. If(head==null)
3. print “underflow”
4. Else
5. print the deleted element ‘head-> data’
6. head= head->link

5. QUEUES USING LINKED LIST

 Queue can also be represented using a singly linked list.
 Linked lists have many advantages compared to arrays.
 In linked list, the Data field contains the elements of queue and Next pointer points to the
next element in the queue.
 Here enqueue operation is accomplished by inserting a new node in the tail or end of
the list.
 Dequeue is done by removing the element from the beginning of the list
 he
ad n
aaa bbb ccc ddd ul
l
fro re
nt ar

Insertion- At the end

Algorithm: Enqueue()
1. Set ptr=head; //initialize the pointer ptr
2. While (ptr->link!=null) do
3. ptr= ptr->link; //ptr now points to the next node
4. ptr->link= temp
5. temp->data=item

Deletion – At the front

Algorithm: DEQUEUE()
1. Start
2. If(head==null)
3. print “underflow”
4. Else
5. print the deleted element ‘head-> data’
6. head= head-> link

6. POLYNOMIAL REPRESENTATION USING LINKED LIST