Data Structure (KCS-301)

Static Implementation of Linked List

Prepared By
N. U. Khan
Computer Science And Engineering Department
IMS Engineering College, Ghaziabad
N U Khan 1
 Type of Linked List
A linked list is a linear collection of
homogeneous data element called nodes. All
nodes are linked by pointers. A linked list can be
of the following types
1. Linear linked list
2. Circular linked list
3. Doubly linked list

N U Khan 2
 Linear Linked List
• A linear linked list consists of a number of homogeneous Data elements called
nodes. A node consists of two types of field
• 1. Information field (Holds the actual information) INFO NEXT
• 2. Next address field (Holds the next address)
• Information field contains actual data in a list and next address field contain
the address of the next node in the list.
• The next address which is used to access the next node is known as a pointer
• Next address field of last node hold “NULL” pointer.
• The entire linked list is referred to and accessed by a pointer which points to
the first node of the list, called head
HEAD
&N1
17 &N2 23 &N3 20 &N4 11 NULL
N1 N2 N3 N4
N U Khan 3
 Circular Linked List
• A Circular linear linked list consists of a number of homogeneous Data
elements called nodes. A node consists of two types of field
• 1. Information field (Holds the actual information) INFO NEXT
• 2. Next address field (Holds the next address)
• Information field contains actual data in a list and next address field contain
the address of the next node in the list.
• The next address which is used to access the next node is known as a pointer
• Next address field of last node hold “Address of first node” pointer.
• The entire linked list is referred to and accessed by a pointer which points to
the first node of the list, called head
TAIL
HEAD
&N4
&N1
17 &N2 23 &N3 20 &N4 11 &N1
N1 N2 N3 N4
N U Khan 4
 Doubly Linked List
• The disadvantage of linear linked list is that traversal is possible in one direction
• A doubly linked list consists of a number of homogeneous Data elements called
nodes. A node consists of three fields BACK INFO NEXT
• 1. Information field (Holds the actual information)
• 2. Next address field (Holds the address of next node)
• 3. Back address field (Hold the address of previous node)
• Next address field of last node hold “NULL” pointer, as there is no node after this.
• Back address field of first node hold “NULL”, as there is no node before this.
• The entire linked list is referred to and accessed by a pointer which points to the
first node of the list, called head. ( This may also be accessed by tail pointer)
HEAD
&N1

N 7 &N2 &N1 5 &N3 &N2 9 &N4 &N3 6 N

N1 N2 N3 N4
• Bidirectional traversal of doubly linked list is useful for implanting page up, an
page down functionality when using doubly linked lists to create editors 5
 Implementation of Linked List
A linked list can be implemented by two methods
• 1. Static implementation of linked list
• Array can be used to implement a linked list
• But array size is defined at compile time (it is static), it
cannot grow dynamically at runtime.
• Entire linked list can be implemented in stack area
• 2. Dynamic implementation of linked list
• An ideal implementation for linked list with the help of
pointer, structure and malloc() function.
• It can be dynamically grow and shrink at run time.
• Entire linked list can be implemented in Heap area and can
be access through stack area
N U Khan 6
 Static Implementation of Linked list

• Data elements of the list are stored in a 1-D array

called data (INFO) (In non sequential order).
• Instead we relax this restriction and allow them
to appear anywhere in a array and in any order.
• In order to remind us of the real order a second
array, NEXT is added. The values in this array are
pointers to elements in the INFO (data) array.

N U Khan 7
N U Khan 8
 The Storage pool
• The storage pool containing all nodes that are not currently being used.
Storage pool is also called the list of available space which consists of
unused memory cells
• Suppose our linked lists are implemented by parallel arrays and suppose
insertions and deletions are to be performed on our linked list. Then the
unused memory cells in the arrays will also be linked together, using ‘Avl’
as its list pointer variable
• GETNODE(X): This function provide in X a pointer to a blank node but if no
node is free then it will return ‘No more node’

• Overflow: When storage pool is empty and we want to insert a data item
into a list pointer ‘head’, this situation is called overflow
• i.e. in the case of overflow
• Avl = ‘NULL’ (and there is an insertion)

• Underflow: When data structure list (head) is empty and we want to

delete data item (INFO) from data structure list, This situation is called
Underflow.
• In this case:
• head = NULL ( and there is a deletion )
N U Khan 9
 Garbage Collection
• Garbage collection is a technique which is used for collect all the deleted
node or unused nodes onto the storage pool list. This technique perform
by the operating system.
• This process is carried out in two phases
• PHASE-1:This process is also known as marking phase. First the computer
run through all lists marked those cells which all currently in use.
• PHASE-2: This phase is also knows as memory compaction. In this phase
all unmarked nodes are returned to the storage pool (Available space list)

• NOTE: If size of nodes are fixed, then in PHASE-2 we simply link all
unmarked node together into a storage pool or available space list.

• Memory compaction:
• When variable size nodes are in used, it is desirable to compact memory,
so that all free nodes (unused nodes) form a contiguous block of memory.
• Compaction of disk space reduce the Average retrieval time

N U Khan 10
 Insertion into a list
• It is easier to make arbitrary insertion and
deletions using a linked list.
• To insert the data ‘J’ between ‘C’ and ‘D’,
following steps are adequate.
1. Get a node where is currently unused. Let its
address be X.
2. Set the INFO field of this node to J
3. Set the NEXT field of X to point to the node after
‘C’.
4. Set the NEXT field of the node containing ‘C’ to X

N U Khan 11