Data Structures with Algorithms 20MCA11

Module -3: Linked List

Module-3: Linked List

• Limitations of array implementation

• Memory Management:

o Static {Stack) and Dynamic (Heap) Memory Allocation

o Memory management functions

- malloc()

- calloc()

- realloc()

- free()

• Linked List:

o Definition,

o Representation

o Operations: getnode() and Free node() operation

• Types: Singly Linked List

o Linked list as a data Structure

o Inserting and removing nodes from a list

• Linked implementations of stacks

• Header nodes

• Array implementation of lists

1
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

1. Limitations of array implementation

• Limitations of array implementation

o Array is Static data Structure

- Memory Allocated during Compile time.
- Once Memo1y is allocated it Cannot be Changed during Run-time
o Wastage of Memory
- if array of large size is defined and elements are less.
o Inserting and removing element is ve1y difficult.

2. Memory Management

• Static (Stack) and Dynamic (Heap) Memory Allocation

No Static memory Dynamic memory allocation

1 Done at compile time. Done at run time.

2 Can't grow and shrink. Can grow and shrink.

3 Uses stack memory Uses Heap memory

4 Faster execution than Dynamic. Slower execution than static.

• What is DMA?

- The process of allocating memory during program execution is called dynamic memory

allocation.

- Dynamic memory allocation allows you to manually handle memory space for your

program.

- When C compiler encounters a request for dynamic allocation of memory through an

appropriate function memory is obtained from a "heap memory".

2
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

• What is heap?

- This is a separate memory area maintained by the compiler which is logical separation in

RAM.

- Initially, entire heap area is available for dynamic allocation, so, the amount of memory

available allocation is called "free list".

• Dynamic memory allocation functions

- malloc()

- calloc()

- realloc()

- free()

 malloc(), calloc(), realloc() - is used to allocate memory dynamically.

 free() - is used to deallocate the memory dynamically.

• Advantages
- The main advantage of dynamic memory allocation is to save memory from unnecessary

wastage because it is allocated as and when required.

• Memory management functions

Function Syntax Parameters

malloc () void* malloc (t_size); 't_size ': size to allocate in bytes.

'nitems': number of objects to allocate.
calloc() void* calloc ( nitems, t_size); 't_size': number of bytes to allocate for
each object.
free() void free (pointer); 'Pointer': name of pointer
'ptr': name of pointer
realloc() void* realloc (ptr, newsize);
'newsize' : new size to allocate in bytes.

3
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

• malloc()
- The name malloc stands for "memory allocation".
- It allocates requested size Bytes in Heap memory.
- Return a starting address of allocated location of type void*.
- Return address must be type casted into pointer of required type.

- Example:

int *ptr =(int*) malloc(sizeof(int));

*ptr = 5.5; Heap

5.5
ptr 260
260
Stack

Figure-1: Dynamic memory allocation using mallocQ.

- Pointer 'ptr' is allocated in stack. DMA function malloc() allocates 4 bytes from
Heap and returns its address to pointer ptr.
#include<stdio.h>
Ql. Example on malloc() function.
#include<conio.h>

void main()
{
int *p;

clrscr();

p = (int*)
malloc(sizeof(int));

if(p==NULL)
{
printf("ERROR\n");
exit(l);
}

4
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

*p=10;

printf("P holds the address= %u\n", p);

printf("P pointing(hold address) value= %d\n", *p); printf("Address of P

getch();
}

Output:
oos
tOH
' DOSBox 0.74, Cpu speed: max 100% cycles, Frames
P hnl<ls thr, ct<l<lrr,ss = 1 1.4
P pninting(hnl<l ct<l<lrr,ss) VctillP-
= 10
A<l<lrr,ss of P = h /.4

• calloc()
- The name calloc stands for "contiguous allocation".
- It allocates multiple blocks of memory each of same size and sets all bytes to zero.

- Example
int *ptr = (int*) calloc (3, sizeof(int));

Heap

ptr 260 260 264 268

Stack

Figure-2: Dynamic memory allocation using callocO.

- Pointer 'ptr' is allocated in stack. DMA function callocO allocates 4 bytes from
Heap and returns its address to pointer ptr.

5
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

Q2. Example on calloc() function.

Write a Program to dynamically allocate an array of 3 locations of int type. Read values
into the locations and display the same.
#include<stdio.h>
#include<conio.h>

void main()
{
int *ptr;
int i;

clrscr();

ptr = (int*) calloc( 3, sizeof(int));

printf("Default value is assigned: \n");

printf("Address - Value\n");
for(i=0; i<3; i++)
printf("%u
%d\n", &ptr[i], ptr[i]);

printf("\nEnter
Elements: \n"),
for(i=0; i<3; i++)
scanf("%d", &ptr[i]);

printf("Elements are: \n");

printf("Address - Value\n");
for(i=0; i<3; i++)
printf("%u %d\n", &ptr[i], ptr[i]);
getch();
}

6
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

Output:

• realloc()
o Helps to increase or shrink the previously allocated memory.

- Assume that you have allocated few blocks of memorv using malloc() or calloc( ).

- Now you may want tu mcrease 01 Jecrease me previously allocated memory, obviously,
you can't go for the earlier two tunct1ons, but we have anomer function in C that can
solve this problem.

- Example

int *ptr = (int*) malloc(sizeof(int));

ptr = (int*) realloc(ptr, 10);

• free()
o This function releases the memory allocated previously by malloc( ) or calloc( ) or
realloc( ).
o free( ) does not return anything.

- Example
Free (ptr)

7
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

Q3. Example on realloc() and free() function.

#include<stdio.h> #include<conio.h>

void main()
{
char *s; clrscr();
s = (char*) malloc(4);
s = "RNS";
printf("Before realloc() s = %s \n", s); s = (char*) realloc(s, 10);
s = "RNSIT-MCA";

printf("\nAfter realloc() s = %s \n", s); free(s);

getch();
}

Output:

8
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

3. Linked List

• Definition
o Linked list is a linear collection of data elements, called nodes, each pointing to the next
node by means of a pointer.
o Each node is composed of data and a reference (link) to the next node.
o Allows for efficient insertion or removal of elements from any position.

• Representation

HEADER

I I Data Link t------ . ,Da_t_a . L_in_k_.t-------'Jol Data Null

• Advantages of Linked Lists

o They are a dynamic in nature which allocates the memory when required.
o Insertion and deletion operations can be easily implemented.
o Stacks and queues can be easilv executed.
o Linked List reduces the access time.

• Disadvantages of Linked Lists

o The memory is wasted as pointers require extra memory for storage.
o No element can be accessed randomly; it has to access each node sequentially.
o Reverse Traversing is difficult in linked list.

• Creating a node

o struct
A variable Listto above List structure is called Node.
created
{ pl, p2;
NODE /* pl and p2 are two nodes */
int data;
struct node *link;
};
typedef struct List NODE;

9
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

Operations: getnode()
A node can be created dynamically.
The method getnode() creates a node dynamically.

NODE *getnode()
{
NODE *p;
p = (NODE*) malloc(sizeof(NODE)); if(p == NULL)
{
printf("\n Memory Not Allocated !");
exit(0);
}
p->link = NULL; return p;
}

• Operations: Freenode()
o Dynamically de-allocate a given node passed as parameter.
void freenode(NODE *temp)
{
free(temp);
}

• Types of linked list:

1. Singly Linked List.

2. Circular Singly Linked List.
3. Doubly linked list
4. Circular Doubly linked list

• Basic operations on Linked List

- Inserting a node
- Deleting a node
- Searching a node
- Traversing a node

10
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

4. Types: Singly Linked List

• Linked list as a data structure

A linked list is a linear data structure, in which the elements are not stored at contiguous
memory locations. The elements in a linked list are linked using pointers as shown in the
below image:

Head

A
Data Next
IJ-( IJ-{ IJ- NULL

In simple words, a linked list consists of nodes where each node contains a data field and a
reference(link) to the next node in the list.

• Inserting and removine: nodes from a

list Operations on Linked List

a). Insert at front (insert in beginning)

b). Insert at end
c). Insert at given position
d). Remove at front (remove in beginning)
e). Remove at end
f). Remove at given position
g). Display

11
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

4.1 Inserting a node in the beginning

• Algorithm:
Stepl: Create New Node and store data.
Step2: Copy stait pointer in the link pai·t of new node.
Step3: Make new node as Sta1ting node.

• Memory Diagram

,,,.
/ ---- --..., .
/ head
I
J
- -
' . I 2 1 NUL
7..---. .
L -
4
_j_ -1
-- -

.
-

C-Function: Insert node at beginning of list.

NODE* insertFront {NODE *start, int item)
{
NODE *newnode·
newnode = getnode\);
newnode->data = item;
newnode->link = start; start= newnode;
printf("\n Node at Beginning Inserted Successfully..\n"); getch();

return start;
}

12
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

4.2 Inserting a node at the End

• Algorithm:
Step1: Create New Node and add data.

Step2: Search for last node and mark it as current 'cur'

Step3: Mark link part of 'cur' to point to 'newnode'.

• Memory Diagram

START

3 2 1
newnode

C Function Inserting a Node at

the end

NODE* insertEnd (NODE start, int item)

{
NODE *newnode,*cur;
newnode = getnode();
newnode->data = item;

if(start==NULL)
{
return newnode;
}
cur= start;
whiLe(cur->Link != NULL) cur= cur->Link;
cur->Link = newnode;
printf("\n Node at End Inserted Successfully ..\n");

return start;
}

13
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

4.3 Inserting a node at a given position

• Memory Diagram to insert node at given position.

start prev

@I 2001
"-I 10!200 H l
201300 I I401
200' •Joo
,
100 \
\ I
301300
400

} Function to insert node at given position in singly list..

newnode->Link =*start int pos int item)
NODE* insertPos(NODE
prev; prev->Link =
{
newnode;
NODE *newnode *prev;
} newnode =
getnode(); newnode-
>data = item;
if(pos==l)
{
newnode->Link = start;
return newnode;
}
prev = start;
for {i = 1; i < pos-1 ; i++) /* Search prev Node for node to be
deleted*/
{
if ( prev ==
NULL) break;
if prev ==NULL)
(
printf ( "\n***Inval id Position ** )
\n"

14
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

4.4 Remove node from Beginning of list

• Algorithm:
Step1: if start is NULL Display: "List is Empty"

Step2: Mark start node with 'cur' pointer (cur= start)

Step3: Copy link part of start to start pointer. (start= start link)

Step4: Display data part of 'cur' Node and remove the node.

• Memory Diagram

- Step1: mark first node by temp

temp
Start

01 02 03 ....,NULL

- Step2: move start to next node and remove temp using free()

Start

02 03 NULL

f.
free(temp)

New Starting Nod.,.

15
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

C-Function: Remove node from front

NODE* removeFront (NODE *start)
{
node *temp;
if (start== NULL)
{
printf (" ..List is Empty.. n);
return start;
}
temp = start;
start = startLink;
printf (" Data removed = %d n temp data );
free
(temp);
return start;
}

4.5 Remove node from End of list

• Algorithm:
Step1: if start is NULL Display: "List is Empty"

Step2: if link part of 'start' is NULL then list has only one node

- Copy 'start' to 'cur' pointer

- Set 'start' with NULL.

- Display Node value and remove the node.

Step3: otherwise Search for 'last' node.

- Mark the previous node with 'prev'.

-Mark link part of 'prev' with NULL and remove Node at 'last'.

16
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

• Memory Diagram
- Step1: Use previous and current pointer to point to last and previous nodes

- Step2: Set link part of previous to NULL and remove last node pointed by current.

START PftEV

3 NULL

C-function:
NODE* removeEnd Remove node from end of list
(NODE *start)
{
node *prevJ *Last;
if ( start == NULL)
{ printf (" .L 1.s'C' is
Empt:y..JJ); return st:art;
}
Last= prev = start;
if ( start Link ==
NULL) start=
NULL;
whiLe ( Last Link ! = NULL) /* search last node */
{
prev = Last;
Last = Last Link J
}
prev Link =
NULL; free
(Last);

17
 Data Structures with Algorithms 20MCA11
Module -3: Linked
List
4.6 Remove node at a given position.

• Memory Diagram to remove a node at a given position

Before removing node

start prev cur

$1,.... 1 00
1

--_10_l_2_0H.20..l... ,.....3 .1.o...-...1.

301 40 1401
100 200 300.,◄400
... ,,.

After removing node

start

$ I....----
-- _10_l_2_0H.20..l... ,. 3 1.o 40I
100200"',
'
◄
., 400
.,

... ... - - - - - - - ... ,,.

'

C-Function: Remove node at given position in a singly list.

NODE* removePos (int pas, NODE *start)

{
NODE*cur, *prev, int i ,
if (start== NULL)
{
printf("---Empty List. Can't delete");
return start;
}
if (pas== 1)
{
printf("\n***JtemDeleted is %d **\n", start->data); start= start->Link,
free (cur); return start;
}

18
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

cur= prev = start;

for ( i = 1; i < pos ; i++)I* Searchprev Node for node to be deleted *I
{
if (cur== NULL) break;
prev = cur;
cur= cur->Link;
}
if (cur== NULL)
{
printf ( "\n***Inval id Position **\n" ); return start;
}
printf ( "\n***Item Deleted is %d **\n", cur->data ); prev->Link
free (cur);
return start;

19
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

4.7 Display Linked List

Function to Display list.

void DispLay(NODE *start)

{
NODE *temp;
if(start == NULL)
{
printf("\nList is Empty\n\n");
return;
}
temp = start;
printf("\nElements are");
printf("***********************************\n");
whiLe(temp != NULL)
{
printf("\n %d ", temp->data); temp= temp->Link;
}
}

20
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

5. Linked Implementations of Stacks

• Problems with Array implementation of stack

- Static: Stack implemented using array works only for fixed number of data values.
- Amount of data must be specified at the beginning of the implementation itself.
- Run time array can't be resized.

• Linked implementations of stacks

- A stack data structure can be implemented by using linked list data structure.
- Works for variable size of data.
- No need to fix the size at the beginning of the implementation.
- In linked list implementation of a stack, every new element is inserted as 'top' element.
- Whenever we want to remove an element from the stack, simply remove the node which
is pointed by 'top' by moving 'top' to its next node in the list.

top

• Stack operations with linked list

o push() : insertFront ( top, item)

The insert front function of linked list perfonns the push operation of stack. 'start'
pointer can be renamed as 'top'. Newnode with given 'item' is inserted at beginning
of list and the 'top' pointer points to the new node.

o pop() : removeFront ( top, item)

The Remove front function of linked list performs the pop operation of stack. First
node in the list is removed and 'top' points to the next node in list for each pop
operation.

o Display(top) :
This function remains same as Display of Linked list. Top will be pointing to the
node which is inserted in last.

21
 Data Structures with Algorithms 20MCA11

6. Header Nodes

Header Nodes
Sometimes it is desirable to keep an extra 1.1ode al the front of a list. Sucha node does n

Cal

Cbl

(cl

ldl

Ir)

fi9ure ,.2.1 Lists with header nodes.

22
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

Cha data strm.:ture more work is needed IO add

d' st d H01 delete anh item from th . e h st .
su
th e count in the header node must b au e · owever,t e number of ite . • si nce
d . h . ms in th
may be obtained directly from the header noe [Link] out travers1 g the entire list e li t
Another example of the use of header nodes 1s the following. Supp ·
. A . I h. ose a fa
assembles machinery out of smaller units. parucu ar mac me (invento
A746) might be compo ed of a number of different part (numbers 8841, K tuniber
1492, G593). This assembly could be r e pre ented by a hst such as the one ill 'A087,
. ustrated •
Figure 4.2.6c, where each item on theI 1st represe ts a omponent and where the he· in
node represents the entire assembly. The empty hst would no longer be repres 11der
the null pointer but ra!her by a list wi!h a single header node. as in Figure 4_ _ l-ed 2
by
Of course:, algonthms for operations such as empty. push. pop, insert and
• '
must be rewn tten to account for the presence of a header node. Most of rem o 1,
. e
the
become a bit more complex. but some. like inserr. become simpler. since an routines
[Link] po·inter 1· s never nuII . W,e 1 eave ht e r e w n· t m· g of the routines as an exercis eixternal
th
reader. The routines insafter and de/after need not be changed at all. In facte ohr e
header nod.e 1s used , m. sa•;"ter and de/after can be used instead of push •w e. n a
andp
· · h 1· · h op, since
.teh fi rst nemm sue a 1st appears m t e node that follows the header node.
m the first node on the list. an
If the info portion of a node can contain a pointer, additional possibilities for the
us_e ofa hea er no e present them elves. For example, the info portion ofa list header
might contam a pointer to the last node in the list as in Fioure
· · J'fi ' e
42 • 6e
• . s
uch an 1mpe-
·
1
mentatwn s1mpI es the representatio of a queue. Until now, two externalpointer.
front and rear, were necessary for a IJst to represent a queue Howeve
· eI efxhternaI pointer to the header node of the list is necessary.· next(q)[Link]
now on 1y a
;mg to the
ront o t e queue. and mfo(q) to its rear. ·
toa "c :t:t : :O !\ i y {.or he _use of the info portion of a Ji ·t header i. as a pointer
for an externalpo1·nter deu _,st unng al traversal process. This would eliminate rhe need
rmg travera .

- Header node is an extra node that contains the address of the first node of the linked list. If
this node contains NULL, then this shows that linked list is empty.
- It is an extra node kept at the front of a list. Such a node does not represent an item in the list.
The information portion is generally used to store extra information like the number of nodes
present in the linked list.
- The space for header node is not allocated until the first node is created. Header node itself
is pointed by a pointer called head (or start) pointer.

4 8 -+-- 10
Start Header Data Link
Node
23
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

7. Array implementation of lists

• Homogeneous lists are implemented using

- Array, structure or union
• A node in a linked list contains two parts:
- data part and link part
• Collections of nodes can be represented using:
- Two Dimensional Array with two columns
- First column represents data part whereas second column represents link part
- Row numbers represents the nodes of list.
• Two or more Lists can be represented in a single 2-Dimensional Array
• Representation of 2-D Array: Example

int List 11] [2] ; // represents list as below

[
• Representation of Data and Link part:
Data List[n][0]
Link List[n][l]
0 1
0
Listl l 10 8
2 120 15,
3 30 -1
4
5
140
100
List2 6
7
20 3
8
160 -1
9
10
Data Link

24
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

• Advantages using array

1. Data accessing is faster
- Any nth element can be accessed directly
- e.g: arr[lO] reads 11th element directly
2. Simple to implement

• Disadvantages using array

1. Can become Full as Size of the array is fixed

- Allocating "extra" space not possible ...
2. Array items are stored contiguously.
- "Not enough contiguous space", will be problem.
3. Space may be wasteful,
- Larger array with few elements where some locations may never be used
4. Insert and delete in middle of elements is tedious.
- For every insertion/deletion we need to shift many elements to left or right side
5. Difficult to maintain sorted order
- For every insertion, many elements are need to be shifted

• Advantages of Linked lists

1. Are Dynamic. List can grow or shrink during execution.

2. Can be maintained in sorted order without shifting elements.
3. Insert and delete at any position are simple.
4. Efficient usage of space.

25
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

Lab Program: 6

Write a C program to simulate the working of a singly linked list providing the following operations:

a. Display & Insert.

b. Delete from the beginning/ end.

c. Delete a given element.

Q4. (Lab Program: 6)

Write a C program to simulate the working of a singly linked list providing the following
operations:
a. Display & Insert. b. Delete from the beginning/ end. c. Delete a given element.

#include <stdio.h>
#include <conio.h>
#include <string.h>

#define max 20

struct Student
{
int data;
struct NODE *link;
};
typedef struct Student NODE;

NODE *getNODE()
{
NODE *p;
p = (NODE*) malloc(sizeof(NODE));
if(p == NULL)
{
printf("\n Memory Not Allocated !");
exit(0);
}
return p;
}

26
 Data Structures with Algorithms 20MCA11

--- Mod-ule -3: Linked- List

// Insert Functions

NODE* insertFront(NODE *start, int data)

{
NODE *newNODE;

newNODE=getNODE();

newNODE->data = data;
newNODE->link = start;

start= newNODE;

return start;
}

// removeFront Functions

NODE* removeFront (NODE *start)

{
NODE *temp;
if (start== NULL)
{
printf ( List is Empty..
11 11

• )

return start;
}

temp= start;
start= start->link;

printf ( Data removed= %d temp->data

11 11

); free (temp);

return start;
}

27
 Data Structures with Algorithms 20MCA11

--- Mod-ule -3: Linked- List

// removeEnd Functions

NODE* removeEnd (NODE *start)

{
NODE *prev, *last;
if (start== NULL)
{
printf ("..List is Empty..");
return start;
}

last= prev = start;

if ( start->link == NULL)
{
printf("Element %d deleted successfully",start->data);
return NULL;
}

while (last->link 1- NULL)/* search last NODE*/

{
preV = last;

last= last->link
}

prev->link = NULL;

printf("Element %d deleted successfully",last->data);

free (last);

return start;
}

28
 Data Structures with Algorithms 20MCA11

--- Mod-ule -3: Linked- List

// removeElement Functions

NODE* removeElement (NODE *start, int element)

{
NODE *cur, *prev;
int i ;

if (start== NULL)
{
printf("---Empty List. Cant delete- - - -");
return start;
}

cur= start;

if (start->data == element)
{
printf("\n***Item Deleted is %d **\n", start->data);
start= start->link,

free (cur);

return start;
}

while(cur != NULL)
{
if(cur->data == element)
{
prev->link = cur->link;
printf("\n NODE with Element: %d deleted successfully!..\n",cur->data);

free(cur);

return start;
}

prev = cur;
cur= cur-
>link;
}

printf("\n\n ** Element not found !!..\n\n");

return start;
}
29
 Data Structures with Algorithms 20MCA11

--- Mod-ule -3: Linked- List

// Display Functions

void Display(NODE *start)

{
NODE *temp;

if(start == NULL)
{
printf("\n List is Empty----\n\n");
return;
}

temp=start;

printf("\n Elements are: ");

printf("***********************************\n");

while(temp!=NULL)
{
printf("%d \t",temp->data);
temp=temp->link;
}
}

void main()
{
int ch, data, pos, element;

/* initialize list to empty */

NODE *start= NULL;

clrscr();
while(l)
{
printf("\n *********LINKED LIST************\n");
printf("\n 1. Insert");
printf("\n 2. Delete at front");
printf("\n 3. Delete at end");
printf("\n 4. Delete a given element");
printf("\n 5. Display");
printf("\n 6. Exit");
printf("\n\n Enter your choice: ");
scanf("%d",&ch);

30
 Data Structures with Algorithms 20MCA11
Module -3: Linked List

clrscr();

switch(ch)
{
case 1:
printf("\n Enter a data: ");
scanf("%d",&data);

flushall();

start= insertFront(start, data);

break;

case 2:
printf("\n ** Deletion at Front ***\n");

start= removeFront(start);
break;

case 3:
printf("\n ** Deletion at End ***\n");

start= removeEnd(start);
break;

case 4:
printf("\n ** Delete a given element ***\n");

printf("Enter an Element to remove:");

scanf("%d", &element);

start= removeElement(start, element);

break;

case 5:
Display(start);
break;

default: exit(0);
}
}
}

31