Data Structure

Lecture 3
Anwar Rashad
Introduction to Linked List

• The everyday usage of the term “list” refers to a linear collection

of data items.
• For example: shopping list;
Disadvantages of Arrays:
• It is relatively expensive to insert and delete elements in an array.
• It occupies a block of memory space, One cannot simply double
or triple the size of an array when additional space is required.
• For this reason, arrays are called dense list and are said to be
static data structures.
Introduction to Linked List

Disadvantages of Arrays:
• The Sequential storage is not either possible or efficient in larger
computer systems because:
• Where a number of users share main memory, there may not be
enough adjacent memory locations left to hold an array. But there
could be enough memory in the shape of small free blocks.
• The data access speed become slow as the size of the array increases.

• To overcome these limitations, linked lists are used.

Linked Lists

• A linked list, or one way list, is a linear collection of data elements,

called nodes, where the linear order is given by means of pointers,
that is, each node is divided into two parts:
1) The First part contains the information of the element, and is called
Information Part.
2) The Second part, called the Link Field or Nextpointer Filed, contains
the address of the next node in the list.
• The pointer of the last node contains a special value, called the null
pointer.
Linked Lists

• A linked list also contains a list pointer variable – called START

or NAME.
• Which contains the address of the first node in the list;
• A list that has no nodes, such a list is called the null list or
empty list and is denoted by the null pointer in the variable
START.
• There are two types of Linked List:
• One-Way list / Single Linked list.
• Two-way list / Double Linked list.
Representation of
Linked Lists in Memory

• Let LIST be a linked list.

• LIST requires two linear arrays – we will call them
• INFO (contain the information part) and
• LINK (contain the next-pointer field of the node of LIST).
• Also LIST requires a variable name – such as START – which contain
the location of the beginning of the list.
• The element of the LIST need not occupy adjacent elements in the
arrays INFO and LINK.
Traversing a Linked List

• Let LIST be a linked list in memory stored in linear arrays INFO and LINK
with START pointing to the first element and NULL indicating the end of
LIST.
• In the algorithm the variable PTR points to the node currently being
processed.
1) Set PTR := START
2) While PTR ≠ NULL
Apply PROCESS to INFO[PTR]
set PTR := LINK[PTR]
[End of loop]
3) Exit
Searching a Linked List

• We are going to discuss two searching algorithms for finding the

location LOC of the node where ITEM first appears in LIST.

• The first algorithm is for unsorted values.

• The second algorithm is for sorted values.
LIST is Unsorted

• Let the data in LIST are unsorted.

• Then one searches for ITEM in LIST by traversing through the list
using a pointer variable PTR and
• Comparing ITEM with the contents INFO[PTR] of each node, one
by one, of LIST.
Algorithm for Searching an
Unsorted Linked List

SEARCH (INFO, LINK, START, ITEM, LOC) [End of Loop]

1) Set PTR := START 3) Set LOC := NULL
2) While PTR ≠ NULL
4) Exit
If ITEM = INFO [PTR], then
set LOC := PTR, and Exit
Else;
set PTR := LINK [PTR]
[End of If Structrue]
LIST is Sorted

• Let the data in LIST are sorted.

• Then one searches for ITEM in LIST by traversing through the list
using a pointer variable PTR and comparing ITEM with the
contents INFO[PTR] of each node, one by one, of LIST.
• We can stop once ITEM exceeds INFO[PTR].
Algorithm for Searching an
Sorted Linked List

SRCHS (INFO, LINK, START, ITEM, LOC) [End of If Structure]

1) Set PTR := START [End of Loop]
2) While PTR ≠ NULL
3) Set LOC := NULL
If ITEM > INFO [PTR], then
set PTR := LINKE[PTR] 4) Exit
Else If ITEM = INFO[PTR], then
set LOC := PTR, and Exit
Else
Set LOC := NULL, and Exit.
Memory Allocation

• Together with the Linked List in memory, a special list is

maintained which consists of Unused memory cells.
• This list, which has its own pointer, is called the list of available
space or the free-storage list or the free pool.
• The unused memory cells in the linked list (Parallel arrays) is
reference by using AVAIL.
Garbage Collection

• Suppose some memory space become reusable because a node

is deleted from a list or an entire list is deleted from a program.

• We want the space to be available for future use.

• One way to bring this about is to immediately reinsert into the
free-storage list.
• This method may be too time-consuming for the operating
system of a computer.
Garbage Collection (Continue…)

• Another way, the operating system of a computer may periodically collect all the
deleted space onto the free-storage list.
• Any technique which does this collection is called Garbage Collection.

• Garbage Collection usually take place in two steps.

• First: The computer runs through all lists, tagging those cells which are
currently in use.
• Second: The computer runs through the memory, collecting all untagged
space onto the free-storage list.
Garbage Collection (Continue…)

• The Garbage collection may take place when there is only some

• Minimum amount of space or no space at all left in the free-storage list.

OR
• When the CPU is idle and has time to do the collection.

• The Garbage collection is invisible to the programmer.

Overflow

• When some new data is to be inserted into a data structure but there is
no available space, i.e., the free-storage list is empty.

• This situation is usually called Overflow, the programmer may handle

overflow by printing the message OVERFLOW.

• Overflow will occur with our linked lists when AVAIL = NULL and there is
an insertion operation.
Underflow

• Underflow refers to the situation where one wants to delete data from a
data structure that is empty.

• The programmer may handle underflow by printing the message

UNDERFLOW.

• Underflow will occur with our linked list when START = NULL, there is a
deletion operation.
Insertion into a Linked List

• Let LIST be a linked list with successive nodes A & B.

• Suppose a node N is to be inserted into the list between node A & B.
• That is, after the insertion node A now points to the new node N, and node
N points to node B.

• The exact situation is, the first node in the AVAIL list will be used for the new
node N. thus a more exact schematic diagram of such an insertion is that;
Insertion into a Linked List

• Three pointer fields are change as follows:

1) The Nextpointer field of node A now points to the new node N, to which
AVAIL previously pointed.
2) AVAIL now points to the second node in the free pool, to which node N
previously pointed.
3) The Nextpointer field of node N now points to node B, to which node A
previously pointed.
 There are also two special cases. If the new node N is the first node in the list,
then START will point to N,
 And if the new node N is the last node in the list, then N will contain the null
pointer.
Insertion Algorithms

• Algorithms which insert nodes into linked lists, has three types.

• First one insert a node at the beginning of the list.

• Second one insert a node after the node with a given location.

• Third one inserts a node into a sorted list.

Inserting at the
Beginning of a List

• Let our linked list is not sorted, & no need to insert a new node in any special
place.
• Then the easiest place to insert the node is 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) Set LINK[NEW] := START
5) Set START := NEW
6) Exit
Inserting after a Given node

• Lets we are given the value of LOC where either LOC is the
location of a node A in a linked LIST OR
• LOC = NULL.
• And N denote the new node.
• If LOC = NULL, then N is inserted as the first node,
• Otherwise, the following algorithm is used.
Inserting after a Given
node in Linked List
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.
[End of If Structure]
5) Exit
Inserting into a
Sorted Linked List
• Let ITEM is to be inserted into a sorted linked LIST.
• Then ITEM must be inserted between node A and B so that

INFO (A) < ITEM ≤ INFO (B)

INSSRT (INFO, LINK, START, AVAIL, ITEM)

1) Call FINDA (INFO, LINK, START, ITEM, LOC)
2) Call INSLOC (INFO, LINK, START, AVAIL, LOC, ITEM)
3) Exit
Inserting into a
Sorted Linked List
FINDA (INFO, LINK, START, LOC, ITEM)
Set SAVE := PTR and PTR := LINK [PTR].
1) If START = NULL, then Set LOC := NULL, and [End of Loop]
Return LOC.
2) If ITEM < INFO[START], then: Set LOC := 5) Set LOC := SAVE
NULL, and Return LOC. 6) Return
3) Set SAVE := START and PTR := LINK [START].
4) While PTR ≠ NULL
If INFO[PTR] > ITEM then
Set LOC := SAVE, and Return LOC.
[End of If Structure]
Deletion from a Linked List

• Let LIST be a linked list with a node N between A and B.

• Suppose node N is to be deleted from the linked list.

• To delete a node from a linked list we have two situations.

• First: Delete a node following a given node.

• Second: Delete a node with a given ITEM of information.
Deleting the node
following a given node
DEL (INFO, LINK, START, AVAIL, LOC, LOCP)
1) If LOCP = NULL, then
Set START := LINK [START]
Else:
Set LINK [LOCP] := LINK [LOC]
[End of If Structure]
2) Set LINK [LOC] := AVAIL and AVAIL := LOC
3) Exit
Deleting the Node with a
Given ITEM of Information

• Let LIST be a linked list in memory, and ITEM is a given information.

• And we want to delete the first node N which contains ITEM.
• First: Find the location LOC of the first node N which contains ITEM and
the location LOCP of the node preceding N.
• Second: Delete the first node N which contains the given ITEM of
information.
Deleting the Node with
a Given ITEM of Information

DELETE (INFO, LINK, START, AVAIL, ITEM) Else:

Set LINK [LOCP] := LINK [LOC]
1) Call FINDB (INFO, LINK, START, ITEM, LOC, LOCP)
[End of If Structure]
2) If LOC = NULL, then Write: ITEM not in list, and
Exit. 4) Set LINK [LOC] := AVAIL and AVAIL := LOC.
3) If LOCP = NULL, then 5) Exit
Set START := LINK [START]
Deleting the Node with
a Given ITEM of Information

FINDB (INFO, LINK, START, ITEM, LOC, LOCP)

3) Set SAVE := START and PTR := LINK [START]
1) If START = NULL, then
Set LOC := NULL and LOCP := NULL, 4) While PTR ≠ NULL
and Return. If INFO [PTR] = ITEM, then
[End of If Structure] Set LOC := PTR and LOCP := SAVE, and Return.
2) If INFO [START] = ITEM, then
[End of If Structure]
Set LOC := START and LOCP := NULL,
Set SAVE := PTR and PTR := LINK [PTR]
and Return.
[End of If Structure] [End of Loop]
5) Set LOC := NULL
6) Return
Header Linked List

• A Header Linked List is a linked list which always contains a special node, called the
header node, at the beginning of the list.

• Two kinds of widely used header lists are:

1) A Grounded Header List is 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.
Two-way Lists

• Linked list we study so far is called one-way list. It can be traverse only from
the beginning with pointer variable START, so we can traverse the list in only
one direction.
• One has immediately access to the next node in the list, but does not have
access to the preceding node.
• Now two-way list, which can be traversed in two directions: in usual forward
direction from beginning to the end of the list.
• OR in the backward direction from the end to the beginning of the list.
Two-way Lists

• A Two-way list is a linear collection of data elements, called nodes, where each node
N is divided into three parts:
• An Information field INFO which contain the data of N.
• A pointer field FORW which contains the location of the next node in the list.
• A pointer field BACK which contains the location of the preceding node in the list.

• The list also required two list pointer variables:

• FIRST, which point to the first node in the list.
• LAST, which points to the last node in the list.
Two-way Header Lists

• The advantages of a two-way list and a circular header list may be combined into
a two-way circular header list.

• The list is circular because the two end nodes point back to the header node.
• It require only one list pointer variable START, which point to the header
node.
END