Linked List Static and Dynamic Memory Allocation

Static variables are declared and named while writing the program. (Space for them exists as long as the program, in which they are declared, is running.) Static variables cannot be created or destroyed during execution of the program in which they are declared.
Dynamic variables are created (and may be destroyed) during program execution since dynamic variables do not exist while the program is compiled, but only when it is run, they cannot be assigned names while it is being written. The only way to access dynamic variables is by using pointers. Once it is created, however, a dynamic variable does contain data and must have a type like any other variable. If a dynamic variable is created in a function, then it can continue to exist even after the function terminates.
Linked Linear List
We saw in previous chapters how static representation of linear ordered list through Array leads to wastage of memory and in some cases overflows. Now we don't want to assign memory to any linear list in advance instead we want to allocate memory to elements as they are inserted in list. This requires Dynamic Allocation of memory and it can be achieved by using malloc() or calloc() function.
But memory assigned to elements will not be contiguous, which is a requirement for linear ordered list, and was provided by array representation. How we could achieve this?

1. For More Visit: Https://www.ThesisScientist.com


Unit 4
Linked List
Static and Dynamic Memory Allocation
In static memory allocation memory is allocated at compile time. If we declare a stack through an array of
100 elements (all integers) then the statement will be :
int stk[100];
This declaration would typically be used if 100 records are to be stored in memory. The moment we make
this declaration 200 bytes are reserved in memory for storing 100 integers in it. However it may so happen
that when we actually run the program we might be interested in storing only 60 integers, even in this case
200 bytes would get reserved in memory which would result in wastage of memory. There may be cases
when we need to store more than 100 records, in this case array would fall short in size.
We can overcome these problems by allocating memory at Run Time (instead of compile time), this is
called Dynamic Memory Allocation. It is done by using Standard Library functions malloc () and calloc ().
Syntax for Allocating memory through malloc :
p = (data type*) malloc (n*size of (<datatype>));

Example 1
p = (int *) malloc (n * 2);
The expression (int *) is used to typecast the address being returned as the address of an integer.
The calloc() function is exactly similar to malloc() except for the fact that it needs two arguments as against
the one argument required by malloc().
Example 2
int *p
p = (int *) calloc (100, 2);
Here 2 indicates that we wish to allocate memory for storing integers, since an integer is a 2 byte entity, and
100 indicates that we want to reserve space for storing 100 integers.
Another difference between malloc() and colloc() is that, by default the memory allocated by malloc()
contains garbage values whereas that allocated by calloc() contains all zeros.
Pointers

2. For More Visit: Https://www.ThesisScientist.com


Pointer is a variable that gives the Address (location or link or reference) of some other variable. As other
variables, pointer also cannot be used before declaration. We can declare the pointer variable as:
datatype *p;
This declaration specifies that p is a pointer variable which, will store the address of variable of particular
datatype. '*' stands for 'value stored at address'. Thus if we declare int *p; then it would mean, the value at
the address contained in p is an integer.
Static and Dynamic Variables
Static variables are declared and named while writing the program. (Space for them exists as long as the
program, in which they are declared, is running.) Static variables cannot be created or destroyed during
execution of the program in which they are declared.
Dynamic variables are created (and may be destroyed) during program execution since dynamic variables
do not exist while the program is compiled, but only when it is run, they cannot be assigned names while it
is being written. The only way to access dynamic variables is by using pointers. Once it is created,
however, a dynamic variable does contain data and must have a type like any other variable. If a dynamic
variable is created in a function, then it can continue to exist even after the function terminates.
Linked Linear List
We saw in previous chapters how static representation of linear ordered list through Array leads to wastage
of memory and in some cases overflows. Now we don't want to assign memory to any linear list in advance
instead we want to allocate memory to elements as they are inserted in list. This requires Dynamic
Allocation of memory and it can be achieved by using malloc() or calloc() function.
But memory assigned to elements will not be contiguous, which is a requirement for linear ordered list, and
was provided by array representation. How we could achieve this?
We have to consider a logical ordered list, i.e. elements are stored in different memory locations but they
are linked to each other and form a logical list as in Fig. 1.1. This link represents that each element has A
1
A
2
A
3
A
4
……
.
A
n
A
1
A
2
A
3
A
4
……
.
A
n

Figure 1.1: Logical List
the address of its logical successor element in the list. We can understand this concept through a real life
example. Suppose their is a list of 8 friends, x1, x2......x8. Each friend resides at different locations of the
city. x1 knows the address of x2, x2 knows the address of x3 and so on .... x7 has the address of x8. If one
wants to go to the house of x8 and he does not know the address he will go to x2 and so on Fig 1.2.
The concept of linked list is like a family despaired, but still bound together. From the above discussion it is
clear that Link list is a collection of elements called nodes, each of x
1
Add.of x
2
x
2
Add.of x
3
X
3
……. X
8 NULLx
1
Add.of x
2
x
2
Add.of x
3
X
3
……. X
8 NULL

Figure 1.2
which stores two items of information:
 An element of the list

3. For More Visit: Https://www.ThesisScientist.com


 A link or address of another node
Link can be provided through a pointer that indicates the location of the node containing the successor of
this list element. The NULL in the last node indicates that this is the last node in the list.
Implementation of Linked List
Link List is a linear Data Structure with the following operations defined on it:
 Insertion of a node at the beginning
 Insertion of a node at the end
 Insertion of a node after a specified node
 Deletion of a particular node from the list
 Traversing of entire link list.
Insertion of a Node at the Beginning
We have a linked list in which the first element is pointed by list pointer.
We can take node data as Input, from user and point this node through temp. Now we can attach temp to the
list by putting address of List in the link field of node pointed by temp Fig. 1.3. Then we can update the …….
NULLlist
temp
…….
NULLlist
temp

Figure 1.3
Insertion of a Node at the End
We traverse the list until NULL (i.e. end of the list) is found. We traverse the list through an additional
pointer 'p' and, fix the start pointer list at the beginning of linked list. When p reaches the end, we will
attach temp to p by putting the address of node pointed by temp in the link field of p Fig. 1.4. NULL
…….
NILLlist
xtemp
p ®………. p ®…………………… p ®
NULL
…….
NILLlist
xtemp
p ®………. p ®…………………… p ®
…….
NILLlist
xtemp
p ®………. p ®…………………… p ®

Figure 1.4


Insertion of a Node After a Specified Node

4. For More Visit: Https://www.ThesisScientist.com


Traverse the list until node with specified value is found or the end of list is found. If end of list is found
then print the message that "Given No. is not present" otherwise insert node pointed by temp between nodes
pointed by p and p -> link (p is used to traverse the list) Fig. 1.5. NULLn
xtemp NULL
p
NULLn
xtemp NULL
p
p ® link
NULLn
xtemp NULL
p
NULLn
xtemp NULL
p
p ® link

Figure 1.5

Deletion of a Node from Linked List
Search the node, which is to be deleted from the list by traversing the list through pointer p. If end of List is
found then print the message the 'Given No. is not found' otherwise store the address of node successor to
the node to be deleted in the link field of p. Free the node to be deleted, Fig. 1.6 NULLnum
Node to be
deleted
NULLnum
Node to be
deleted

Figure 1.6

Concatenation of Linked Lists
Consider a case where we have two Linked Lists pointed to by two different pointers, say p and q
respectively, and we want to concatenate 2nd list at the end of the first list. We can do it by traversing first
list till the end and then store the address of first node in the second list, in the link field of last node of first
list. Suppose we are traversing first list by pointer temp, then we can concatenate the list by the
statement(Fig. 1.7)
temp -> link = q;

5. For More Visit: Https://www.ThesisScientist.com

NULL
(a)
NULL
Temp ®
(b)
NULL
q ®
p ®
q ®
p ® NULL
(a)
NULL
Temp ®
(b)
NULL
q ®
p ®
q ®
p ®

Figure 1.7 (a) Lists before Concatenation, (b) List after Concatenation
Applications of Linked List
Linked Stack
Stack is a very common and popular linear data structure. Since it is a linear data structure it can be
represented through Array and linked list. We have studied in previous chapters the Array representation of
stacks. It has some drawbacks, major one being fixed size. We have to cope with memory wastage and
conditions of overflow while implementing stacks through array. In this section we implement stacks
through linked list.
Linked list uses dynamic memory allocation. Hence, it overcomes the drawbacks of array representation of
stack.
In stack we maintain a pointer 'top' of struct node type. All the insertions and deletions are made on one
end, which is to be pointed by 'top' as in Fig. 1.8. NULL
top ®
NULL
top ®

Figure 1.8: Stack
Functions for insertion (push operation) and deletion (pop operation) are given below:

6. For More Visit: Https://www.ThesisScientist.com


Linked Queue
Like stack, queue is also very popular linear Data structure and can be represented by linked List. We have
to maintain two pointers 'front and rear' of struct node type Fig 15.9. We have to increment 'rear pointer' on
insertion and increment 'front' on deletion from the Queue. NULL
rearfont
NULL
rearfont

Figure 1.9: Linked Queue
Polynomial Representation
Polynomials in general are represented by the following equation:
f(x) = cix
e
i+ ci-1x
e
i-1+....+c1x
e
1
where Ci are non zero coefficients of variable x And ei are exponents such that
ei > ei-1 > ei-2 >.........> e1 > 0.
For example :
F1(x) = 3x
7
-7x
5
+3x
2
+1
F2(x) =5x
8
+6x
5
+4x
2
+13
These Polynomials can be added to form another Polynomial
Let f3(x) = f1(x) +f2(x)
f3(x) = 5x
8
+ 3x
7
–x
5
+ 7x
2
+14
This is achieved by adding coefficients of variables with same exponent value.
These Polynomials can be maintained using a Linked List. To achieve this each term will be represented by
a node and each node should consist of three elements namely coefficients, exponents and a link to the next
term (represented by another node)

For instance, the polynomial
f(x)= 4x
11
-3x
9
+2x
3
+1 will be stored as :



ii)
iii) 4 11 -3 9 2 3 1 0 NULL
f (x)
4 11 -3 9 2 3 1 0 NULL
f (x)
5 8 z Now exp (p) > exp (q) Hence-4 5 5 8 z Now exp (p) > exp (q) Hence-4 5
5 8 z -4 5 -4 5 9 3 5 8 z -4 5 -4 5 9 3
Coef. Exp.LinkCoef. Exp.Link

7. For More Visit: Https://www.ThesisScientist.com


iv)

v)
Doubly Linked Lists
In the single linked list each node provides information about where the next node is in the list. It faces
difficulty if we are pointing to a specific node, then we can move only in the direction of the links. It has no
idea about where the previous node lies in memory. The only way to find the node which precedes that
specific node is to start back at the beginning of the list. The same problem arises when one wishes to
delete an arbitrary node from a single linked list. Since in order to easily delete an arbitrary node one must
know the preceding node. This problem can be avoided by using Doubly Linked List, we can store in each
node not only the address of next node but also the address of the previous node in the linked list. A node
in Doubly Linked List has three fields Fig 1.10.
 Data
 Left Link
 Right Link L LINK DATA R LINKL LINK DATA R LINK

Figure 1.10: Node of Doubly Linked List
Left link keeps the address of previous node and Right Link keeps the address of next node. Doubly Linked
List has following property figure 15.11.
p=p->llink->rlink=p->rlink->llink. L LINK R LINK
p
L LINK R LINKL LINK R LINKL LINK R LINK
p

Figure 15.11
This formula reflects the essential virtue of this structure, namely, that one can go back and forth with equal
ease.
Circular Linked List
Circular Linked List is another remedy for the drawbacks of the Single Linked List besides Doubly Linked
List. A slight change to the structure of a linear list is made to convert it to circular linked list; link field in
the last node contains a pointer back to the first node rather than a NULL. See Figure 1.12

Figure 1.12: Circular Linked List 5 8 z -4 5 -4 5 9 3 7 2
Now p exhorted Hence,
5 8 z -4 5 -4 5 9 3 7 2 5 8 z -4 5 -4 5 9 3 7 2
Now p exhorted Hence,
5 8 z -4 5 9 3 7 2 2 1 5 8 z -4 5 9 3 7 2 2 1