Linked List

Data Structure and Algorithms

Topics
Singly Linked Lists and Chains, Representing
Chains in C, Polynomials, Sparse Matrix,
Doubly Linked Lists, Circular & Header Linked
Lists

Linked Lists
A linked list, is a linear collection of data

elements called nodes, where the linear order

is given by means of pointers.
It is the second most used data structure after
array

Advantages of Linked Lists

They are a dynamic in nature which allocates

the memory when required.

Insertion and deletion operations can be
easily implemented.
Stacks and queues can be easily executed.
Linked List reduces the access time.

Disadvantages of Linked Lists

The memory is wasted as pointers require

extra memory for storage.

No element can be accessed randomly; it has
to access each node sequentially.
Reverse Traversing is difficult in linked list.

Linked List Memory

Representation
In memory the linked list is stored in scattered cells (locations).The memory

for each node is allocated dynamically means as and when required. So the
Linked List can increase as per the user wish and the size is not fixed, it can
vary.
Suppose first node of linked list is allocated with an address
1008. Its graphical representation looks like the figure
shown below

Suppose next node is allocated at an address 506, so the list

becomes

Linked List Memory

Representation
Suppose next node is allocated with an address with an

address 10, the list become,

Address

Comments

links

1008

Root & single

element

506

506

1st element insertion

10

10

2nd element insertion

NULL

Linked List Memory

Representation contd..
Let LIST be the linked list. First of all,
LIST requires two linear arrayscall
them as INFO and LINK. INFO[K]
represents the information part and
LINK[K] represents the next pointer
field of the node of LIST for Kth
element. LIST also requires 2variables
such as START which contains the
location of the beginning of the list and
the next pointer sentinel denoted by
NULL which indicates the end of the
list. Since the subscript of the arrays
INFO and LINK will usually be
positive, so NULL should be treated as
0 unless otherwise stated.

Types of Linked Lists

Singly Linked Lists

Doubly Linked Lists

Circular Linked List

Double Linked List

Important Concepts:
LinkEach Link of a linked list store the data
NextEach Link of a linked list contain a link to next link
PrevEach Link of a linked list contain a link to previous
link
Linked List A Linked List contains the connection link
to the first Link called First and to the last link called Last.

Circular Linked List

Circular Linked List is a variation of Linked list in which first
element points to last element and last element points to first
element. Both Singly Linked List and Doubly Linked List can
be made into as circular linked list.
Singly Linked List as Circular In singly linked list, the next
pointer of the last node points to the first node.

Circular Linked List

Doubly Linked List as Circular In doubly linked list, the
next pointer of the last node points to the first node and the
previous pointer of the first node points to the last node
making the circular in both directions.

Linked List Basic

Operation
Insertionadd an element at the beginning of the list.
Deletiondelete an element at the beginning of the list.
Insert Last-add an element in the end of the list.
Delete Lastdelete an element from the end of the list.
Insert Afteradd an element after an item of the list.
TraverseTraverse and display the complete list in forward

manner.
Searchsearch an element using given key or data item.
Deletedelete an element using given key or data item.
Traverse Backwarddisplaying complete list in backward manner.
Applicable for double and circular linked list

Traverse Algorithm
1.Traverse Algorithm
Consider LIST be a linked list in memory
stored in linear arrays INFO and LINK with
START pointing to the first element, NULL
indicating the end of the list and PTR is the
pointer that points to the node currently
being processed. Below is the algorithm to
traverse through all nodes exactly once and
write the node data element and can be
represented using procedure
PRINT(INFO,LINK,START)
1.Set PTR :=START
2.Repeat steps 3 and 4 while PTR<>NULL
3. PRINT INFO[PTR]
4. PTR:=LINK[PTR]
[PTR pointing to next node]
5.Exit

2.Find count of no. of element in a linked

list
Consider LIST be a linked list in memory
stored in linear arrays INFO and LINK
with START pointing to the first element,
NULL indicating the end of the list and
PTR is the pointer that points to the node
currently being processed. Below is the
algorithm to find the number of NUM
elements in the linked list and can be
represented using procedure
COUNT(INFO,LINK,START,NUM)
1.Set PTR: = START
2.SetCNT=0
3.Repeat steps 4 and 5 while PTR<>NULL
4. IF(INFO[PTR]=NUM) THEN
Set
CNT=CNT+1
5. PTR=LINK[PTR] [PTR pointing to
next node]
6.PRINT CNT
7.Exit

Searching Algorithm
Unsorted List
Consider LIST be a linked list in memory stored in
linear arrays INFO and LINK with START
pointing to the first element, NULL indicating the
end of the list and PTR is the pointer that points to
the node currently being processed and ITEM is
the information given. Below is the algorithm to
find the location LOC of the node where ITEM
first appears in the LIST and can be represented by
SEARCH(INFO,LINK,START,ITEM)
1.Set PTR = START
2.Set LOC=NULL
3.Repeat steps 4 and 5 while PTR <> NULL
4.IF (ITEM= INFO[PTR]) THEN LOC=PTR
EXIT
5.ELSE PTR=LINK[PTR]
6.Exit

Sorted List
Consider LIST be a linked list in memory
stored in linear arrays INFO and LINK with
START pointing to the first element, NULL
indicating the end of the list and PTR is the
pointer that points to the node currently being
processed and ITEM is the information given.
Below is the algorithm to find the location
LOC of the node where ITEM first appears in
the LIST and can be represented by
SEARCH_SL(INFO,LINK,START,ITEM)
1.Set PTR = START
2.Set LOC = NULL
3.Repeat 4 while PTR<>NULL
4.IF(ITEM<INFO[PTR]) then Set
PTR=LINK[PTR]
else
IF(ITEM=INFO[PTR])
then LOC=PTR
EXIT
else EXIT

Garbage Collection
The maintenance of the linked list in
memory assumes the possibility of inserting
new nodes into the list requires some
mechanism which provides unused memory
space for the new nodes. Analogously some
mechanism is required where by the memory
space of deleted nodes becomes available
for further use. Together with the linked list
in memory, a special list is maintained which
consists of unused memory cells. The list,
which has its own pointer, is called the list
of available space or the free storage list or
free pool. Suppose the linked list is
implemented by parallel arrays and then the
unused memory cells in the array will be
also linked together to form linked list using
AVAIL as its list pointer variable.

Garbage Collection contd..

Suppose some memory space becomes reusable because a
node is deleted from a list or an entire list is deleted from
the program. Clearly we want the space to be available for
future use. One way to bring this is to immediately
reinsert the space into the free-storage list. This is what
will do when we implement the linked list by means of
linear arrays. However, the method may be too timeconsuming for the operating system of a computer and
which may choose an alternative method as follows.

Garbage Collection contd..

The operating system of a computer may periodically collect all the

deleted space on to the free storage list and the techniques does this
collection is called garbage collection. It is invisible to the
programmer. It takes 2 steps
1st The computer runs through all the list, tagging those cells which
are currently in use
2nd computer run through the memory, collecting all untagged
space onto the free-storage list The garbage collection take place
whenThere is only some minimum amount of space
No space at all left in the free-storage list
CPU is idle and has time to do the collection

Overflow and Underflow

The situation is called
Overflow when the data
are inserted into a data
structure but there is no
available space i.e.free
storage list is empty. This
will happen when AVAIL
is NULL and insertion
operation is initiated.

The situation is called

Underflow when deletion
operation is initiated when the
data structure is empty. This
will happen when START is
NULL and deletion operation
is initiated.

Insertion Algorithm

Various situations are possible for inserting a node in a linked list. They are
as following
Inserts node at the beginning of the list
Inserts node after the node with a given location
Inserts a node into a sorted list
All our algorithms assume that the linked list is in memory in the form
LIST(INFO,LINK,START,AVAIL)
and that the variable ITEM contains new information to be added to the list.
All algorithms will include following steps:
If AVAIL=NULL, then print OVERFLOW
NEW:=AVAIL, AVAIL=LINK[AVAIL]
INFO[NEW]:=ITEM

Inserting at the beginning of

the list

INSFIRST(INFO, LINK,START,AVAIL,ITEM)
1.If AVAIL=NULL, then Write: OVERFLOW and Exit
2.Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
3.Set INFO[NEW]:=ITEM
4.LINK[NEW]:=START
5.START:=NEW
6.Exit

Inserting After a Given Node

INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM)

1. If AVAIL=NULL then WRITE:OVERFLOW and Exit
2. Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
3. Set INFO[NEW]:=ITEM
4. If LOC=NULL then
Set LINK[NEW]:=START and START:=NEW
Else:
Set LINK[NEW]:=LINK[LOC] and LINK[LOC]:=NEW
5.Exit

Inserting into a sorted linked list

1.IF(START=NULL) THEN Set LOC=NULL and Return
2.IF(ITEM<INFO[START]) THEN LOC=NULL and Return
3.Set SAVE=START and PTR=LINK[START]
4.REPEAT 5 and 6 WHILE PTR<>NULL
5. IF ITEM<INFO[PTR] THEN Set LOC=SAVE and Return
6. Set SAVE = PTR and PTR=LINK[PTR]
7.Set LOC=SAVE
8.Call INSLOC(INFO,LINK,START,AVAIL,LOC,ITEM)
9.Return

Deletion Algorithm

The three pointers fields are changed as follows:

1.The next pointer field of first node now points to second node, where node N
previously pointed.
2.The next pointer field of N now points to the original first node in the free
poll, where AVAIL previously pointed.
3.AVAIL now points to the deleted node N.

Deletion from a node following a given

node

Deletion from a node following a given

node
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
1.If LOCP=NULL then,
Set START:=LINK[START]
Else:
Set LINK[LOCP]:=LINK[LOC]
2.Set LINK[LOC]:=AVAIL and AVAIL:=LOC
3.Exit

Header Linked List

A header linked list is a list which always contains a
special node, called the header node, at the beginning of
the list. The following are two kinds of widely used
header lists:
1.A grounded header list is a header list where the last node
contains the null pointer
2.A circular header list is a header list where the last node
points back to the header node.

Circular Header List

Algorithm
Consider LIST to be a circular header
linked list in memory. START pointing to
the first element, NULL indicating the
end of the list and PTR is the pointer that
points to the node currently being
processed. Below is the algorithm to
traverse through all nodes exactly once
and write the node data element
1.SetPTR=LINK[START]
2.Repeat steps 3 and 4 while
PTR<>START
3.PRINT INFO[PTR]
4.PTR=LINK[PTR]
5.Exit

Consider LIST to be a circular header

linked list in memory with START pointing
to the first element, specific ITEM info is
given, NULL indicating the end of the list
and PTR is the pointer that points to the
node currently being processed. Below is
the algorithm to find the location LOC in
LIST which contains the ITEM. It can be
represented using procedure
SEARCHCHL(INFO,LINK,START,ITEM)
1.SetLOC=NULL
2.Repeat step3 while PTR<>START AND
INFO[PTR]<>ITEM
3.SetPTR=LINK[PTR]
4.IF(INFO[PTR]=ITEM)THEN
Set LOC=PTR
ELSE
Set LOC=NULL

Circular Header List Algorithm

cont
Delete the first node N which contains ITEM Consider LIST to be a circular
header linked list in memory with START pointing to the first element, specific
ITEM info is given, NULL indicating the end of the list and PTR is the pointer that
points to the node currently being processed. Below is the algorithm to delete the
first node N which contains ITEM. It can be represented using procedure
DELLOCHL(INFO,LINK,START,AVAIL,ITEM)
1.Set SAVE = START and PTR=LINK[START]
2.Repeat steps 3 while PTR<>START AND INFO[PTR]<>ITEM
3.Set SAVE=PTR and PTR=LINK[PTR]
4.IF(INFO[PTR]=ITEM) THEN Set LOC=PTR and LOCP=SAVE ELSE Set
LOC=NULL and LOCP=SAVE
5.IF(LOC=NULL) THEN PRINT(ITEM not exist) and EXIT
6.Set LINK[LOCP]=LINK[LOC]
7.Set LINK[LOC]=AVAIL and AVAIL=LOC
8.Exit

Double Linked List

Double Linked List Deletion Algorithm

Suppose we are given the location LOC of a node N in LIST and want to delete N from the
list. We assume that LIST is a two-way circular header list. Note that PREV[LOC] and
NEXT[LOC] are the locations respectively of the nodes which precede and follow node
N. So N is deleted from the list by changing the following pair of
pointers: NEXT[PREV[LOC]]=NEXT[LOC] and PREV[NEXT[LOC]]=PREV[LOC] The
deleted node N is then returned to the AVAIL list by the assignments: NEXT[LOC]=AVAIL
and AVAIL=LOC
1.SetNEXT[PREV[LOC]]=NEXT[LOC] and PREV[NEXT[LOC]]=PREV[LOC]
2.SetNEXT[LOC]=AVAIL and AVAIL=LOC
3.Exit

Double
Linked
List
Insertion
Algorithm
Suppose we are given the locations LOCA and LOCB of adjacent
nodes A and B in LIST and wanted to insert a given ITEM of
information between nodes A and B. As with a single linklist, we
first remove the first node N from the AVAIL list, using the
variable NEW to keep track of its location and then copy the
data ITEM into the node N i.e.we set: NEW=AVAIL,
AVAIL=NEXT[AVAIL], INFO[NEW]=ITEM As shown in the picture,
the node N with contents ITEM is inserted into the list by
changing the following four pointers: NEXT[LOC]=NEW,
NEXT[NEW]=LOCB, PREV[LOCB]=NEW and PREV[NEW]=LOCA
1.IF(AVAIL=NULL) THEN PRINT(OVERFLOW) and EXIT
2.NEW=AVAIL, AVAIL=NEXT[AVAIL], INFO[NEW]=ITEM
3.NEXT[LOCA]=NEW, NEXT[NEW]=LOCB, PREV[LOCB]=NEW
and PREV[NEW]=LOCA 4.Exit

Sparse Matrix
A sparse matrix is a two-dimensional array in which most

of the elements are zero or null. It is a wastage of memory

and processing time if we store null values or 0 of the
matrix in an array. To avoid such circumstances different
techniques are used such as linked list.
N-square sparse matrices is called triangular matrix. A
square matrix is called lower triangular if all the entries
above the main diagonal are zero. Similarly, a square
matrix is called upper triangular if all the entries below the
main diagonal are zero.

Sparse Matrix cont

Sparsematrixcanberepresentedusingalistofsuc

hnodes,onepernon
zeroelementofthematrix.Forexample,considert
hesparsematrix

Thelinkedlistcanberepresentedusinglinkedlistasshow
nbelow