www.bookspar.

com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS

LINKED LISTS
Contents:
Linked lists
Inserting and removing nodes from a list
Linked implementation of stacks
getnode and freenode operations
Linked implementation of queues
Liked list as a data structure
Examples of list operations
List implementation of priority queues
Header nodes
Lists in C
Array implementation of lists
Limitations of the array implementation
Allocating and freeing dynamic variables
Linked lists using dynamic variables
Queues as lists I n C
Examples of list operations in C
Noninteger and nonhomogeneous lists
Comparing the dynamic and array implementations of lists
Implementing header nodes

Let us discuss about the drawbacks of stacks and queues. During implementation,
overflow occurs. No simple solution exists for more stacks and queues. In a sequential
representation, the items of stack or queue are implicitly ordered by the sequential
order of storage.
If the items of stack or queue are explicitly ordered, that is, each item contained
within itself the address of the next item. Then a new data structure known as linear
linked list. Each item in the list is called a node and contains two fields, an
information field and a next address field. The information field holds the actual
element on the list. The next address field contains the address of the next node in the

1
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS

list. Such an address, which is used to access a particular node, is known as a pointer.
The null pointer is used to signal the end of a list. The list with no nodes – empty list
or null list. The notations used in algorithms are:
If p is a pointer to a node, node(p) refers to the node pointed to by p. Info(p) refers
to the information of that node. next(p) refers to next address portion. If next(p) is not
null, info(next(p)) refers to the information portion of the node that follows node(p) in
the list.
Inserting and removing nodes from a list
A list is a dynamic data structure. The number of nodes on a list may vary
dramatically and dynamically as elements are inserted and removed. For example, let
us consider a list with elements 5, 3 and 8 and we need to add an integer 6 to the front
of that list. Then,
p=getnode();
info(p)=6;
next(p)=list;
list=p;
Similarly, for removing an element from the list, the process is almost exactly
opposite of the process to add a node to the front of the list. Remove the first node of
a nonempty list and store the value of info field into a variable x. then,
p=list;
list=next(p);
x=info(p);
Linked implementation of stacks
The operation of adding an element to the front of a linked list is similar to that of
pushing an element onto a stack. A stack may be represented by a linear linked list. If
an external pointer s points to such a linked list, the operation push(s,x) may be
implemented by:
p=getnode();
info(p)=x;
next(p)=s;
s=p;

2
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS

Similarly, empty(s) can also be tested. Linked implementation of queue can be

achieved in the same fashion. getnode creates a new node. freenode destroys a node.
As and when a new node is required, getnode is called.
getnode and freenode operations
The getnode operation removes the first node from this list and makes it available
for use. The freenode operation adds a node to the front of the list, making it available
for reallocation by the next getnode. The list of available nodes is called the available
list.
Linked implementation of queues
We know that items are deleted from the front of a queue and inserted at the rear.
Let a pointer to the first element of a list represent the front of the queue q.front.
Another pointer to the last element of the list represents the rear of the queue q.rear.
empty(q) and x=remove(q) are similar to empty(s) and x=pop(s) of stack respectively.
Both q.front and q.rear must be null in an empty queue.
Disadvantages - A node in a linked list occupies more storage than a
corresponding element in an array. The additional time spent in managing the
available list for each addition and deletion of an element. All the stacks and queues
of a program have access to the same free list of nodes. Nodes not used by one stack
may be used by another. An item is accessed in a linked list by traversing the list from
its beginning. To access nth item, list implementation requires n operations. It is
necessary to pass through each of the first (n-1) elements before reaching the nth
item.
Advantages - The advantage of a list over an array occurs when it is necessary to
insert or delete an element in the middle of a group of other elements.
Linked list as a data structure
insafter(p,x) and delafter(p,x) denote the inserting and deleting operations of an
item x into a list after a node pointed to by p.
Let insafter(p,x) denote the operation of inserting an item x into a list after a node
pointed by p. this operation is implemented as follows:
q=getnode();
info(q)=x;

3
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS

next(q)=next(p);
next(p)=q;
Let delafter(p.x) denote the operation of deleting the node following node(p) and
assigning its contents to the variable x. this operation may be implemented as follows:
q=next(p);
x=info(q);
next(p)=next(q);
freenode(q);
There is no way to proceed from a given node to its predecessor in a linear list
without traversing from the beginning. So, insbefore() and delbefore() does not exists.
Examples of list operations
It is possible to delete all occurrences of the number 4 from a list. To implement a
list where the items are ordered, so that smaller items precede larger ones ordered list.
List implementation of priority queues
For an ascending priority queue, insertion (pqinsert) is implemented by push
operation and deletion by pop operation (pqmindelete), which removes the first element
from the list. Similarly for a descending priority queue, we have pqmaxdelete. This
requires an average of approximately n/2 nodes for insertion, but only one node for
deletion. In an unordered list, a list requires examining only one node for insertion but
requires examining n nodes for deletion. Thus, an ordered list is somewhat more efficient
than an unordered list in implementing a priority queue.
Header nodes
An extra node at the front of the list, which does not represent an item in the list is
called header node / list header. info portion is unused or used for keeping global
information about the number of nodes in the list, excluding itself. An empty list may
be representing with a single header node. Header node may represent an entire
assembly and following nodes may represent each components. Correspondingly the
implementation details follows.

4
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS

Lists in C
Array implementation of lists
A group of 500 nodes in an array node can be declared as follows:
#define NUMNODES 500
struct nodetype{
int info, next;
};
struct nodetype node[NUMNODES];

5
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS

The above figure shows the array of nodes containing four linked lists. List1
contains 3,7,14,6,5,37,12 starting at node[16]. The null pointer is represented by -1 in
the next field. A global variable avail is used to point to the available list initially, as
all nodes are unused.
avail=0;
for(i=0;i<NUMNODES-1;i++)
node[i].next=i+1;
node[NUMNODES-1].next=_1;
The getnode is a function that removes a node from the available list and returns a
pointer to it:
int getnode(void)
{
int p;
if(avail==-1){
printf(“overflow”);
exit(1);
}
p=avail;
avail=node[avail].next;
return(p);
}
The freenode function accepts a pointer to a node and returns that node to the
available list:
void freenode(int p)
{
node[p].next=avail;
avail=p;
return;
}

6
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS

The routine insafter accepts a pointer p to a node and an item x as parameters. It

first ensures that p is not null and then inserts x into a node following the node pointed to
by p:
void insafter(int p, int x)
{
int q;
if(p==-1){
printf(“void insertion”); //no insertion
return;
}
q=getnode();
node[q].info=x;
node[q].next=node[p].next;
node[p].next=q;
return;
}
The routine delafter(p,px), called by the statement delafter(p,&x), deletes the node
following node(p) and stores its contents in x:
void delafter (int p, int *px)
{
int q;
if((p==-1)||(node[p].next==-1)){
printf(“void deletion”); //no deletion
return;
}
q=node[p].next;
*px=node[q].info;
node[p].next=node[q].next;
freenode(q);
return;
}

7
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS

Limitations of the array implementations

A fixed set of nodes represented by an array is established at the start of the
execution. The number of nodes that are needed cannot be predicted when a program
is written. The number of nodes declared must remain allocated to the program
throughout its execution. A solution could be allowing nodes that are dynamic, rather
than static. The storage for nodes that are no longer in use is available for another
purpose. It is possible that storage can be allocated and freed dynamically using
dynamic variables in C.
We have seen the array implementation of queue previously. Now, in linked list
implementation, the empty queue is represented by front and rear both equaling the
null pointer. Similarly, inserting an element and deleting the first element can also be
implemented. place (list,x) can be used, where list points to a sorted list and x is an
element to be inserted into its proper position within the list (for pqinsert). We can
write insend(plist,x) to insert the element x at the end of a list list. search(list,x)
returns a pointer to the first occurrence of x within the list list and NULL if x does not
exists. remvx() removes all nodes whose info field contains the value x. Non integer
lists and nonhomogeneous lists (those that contain nodes of different types) can also
be implemented.
Implementing header nodes
It is also possible for header nodes to be declared as variables separate from the set of
list nodes. This is particularly useful when the header contains information of a different
type than the data in list nodes. For example, consider the following set of declarations:
struct node{
char info;
struct node *next;
};
struct charstr{
int length;
struct node *firstchar;
}; struct charstr s1,s2;
*****

8
www.bookspar.com | VTU NOTES | QUESTION PAPERS | NEWS | RESULTS | FORUMS