Topics

◆ Introduction
◆ Definitions
◆ Classification of Data Structures
◆ Arrays and Linked Lists
◆ Abstract Data Types [ADT]
• The List ADT
◆ Array-based Implementation
◆ Linked List Implementation
◆ Cursor-based Implementation
◆ Doubly Linked Lists

1
Data Structure [Wikipedia]

◆ Data Structure is a particular way of storing and

organizing data in a computer so that it can be used
efficiently.
◆ Different kinds of data structures are suited to different
kinds of applications.
◆ Storing and retrieving can be carried out on data stored in
both main memory and in secondary memory.

2
Data Structure Classification
◆ Primitive / Non-primitive
• Basic Data Structures available / Derived from Primitive Data
Structures
◆ Homogeneous / Heterogeneous
• Elements are of the same type / Different types
◆ Static / Dynamic
• memory is allocated at the time of compilation / run-time
◆ Linear / Non-linear
• Maintain a Linear relationship between element

3
ADT - General Concept

◆ Problem solving with a computer means processing data

◆ To process data, we need to define the data type and the
operation to be performed on the data
◆ The definition of the data type and the definition of the
operation to be applied to the data is part of the idea
behind an Abstract Data Type (ADT)

4
ADT - General Concept

◆ The user of an ADT needs only to know that a set of

operations are available for the data type, but does not
need to know how they are applied
◆ Several simple ADTs, such as integer, real, character,
pointer and so on, have been implemented and are
available for use in most languages

5
Data Types

◆ A data type is characterized by:

• A set of values
• A data representation, which is common to all these
values, and
• A set of operations, which can be applied uniformly to all
these values

6
Primitive Data Types
◆ Languages like ‘C’ provides the following primitive
data types:
• boolean
• char, byte, int
• float, double
◆ Each primitive type has:
• A set of values
• A data representation
• A set of operations
◆ These are “set in stone”.

7
ADT Definition [Wikipedia]

◆ In computer science, an abstract data type (ADT) is a

mathematical model for a certain class of data structures
that have similar behavior.
◆ An abstract data type is defined indirectly, only by the
operations that may be performed on it and by
mathematical constraints on the effects (and possibly
cost) of those operations.

8
ADT Definition [Wikipedia]
◆ An ADT may be implemented by specific data types or
data structures, in many ways and in many programming
languages; or described in a formal specification
language.
◆ example, an abstract stack could be defined by three
operations:
• push, that inserts some data item onto the structure,
• pop, that extracts an item from it, and
• peek, that allows data on top of the structure to be examined
without removal.

9
ADT in Simple Words

◆ Definition:
• Is a set of operation
• Mathematical abstraction
• No implementation detail
◆ Example:
• Lists, sets, graphs, stacks are examples of ADT along
with their operations

10
Why ADT?
◆ Modularity
• divide program into small functions
• easy to debug and maintain
• easy to modify
• group work
◆ Reuse
• do some operations only once
◆ Easy to change the implementation
• transparent to the program

11
The List ADT
◆ The List is an
• Ordered sequence of data items called elements
• A1, A2, A3, …,AN is a list of size N
• size of an empty list is 0
• Ai+1 succeeds Ai
• Ai-1 preceeds Ai
• Position of Ai is i
• First element is A1 called “head”
• Last element is AN called “tail”

12
Operations on Lists

◆ MakeEmpty
◆ PrintList
◆ Find
◆ FindKth
◆ Insert
◆ Delete
◆ Next
◆ Previous

13
List – An Example

◆ The elements of a list are 34, 12, 52, 16, 12

• Find (52) -> 3
• Insert (20, 4) -> 34, 12, 52, 20, 16, 12
• Delete (52) -> 34, 12, 20, 16, 12
• FindKth (3) -> 20

14
List - Implementation

◆ Lists can be implemented using:

• Arrays
• Linked List
• Cursor [Linked List using Arrays]

15
Arrays

◆ Array is a static data structure that represents a collection

of fixed number of homogeneous data items or
◆ A fixed-size indexed sequence of elements, all of the
same type.
◆ The individual elements are typically stored in
consecutive memory locations.
◆ The length of the array is determined when the array is
created, and cannot be changed.

16
Arrays

◆ Any component of the array can be inspected or updated

by using its index.
• This is an efficient operation
• O(1) = constant time
◆ The array indices may be integers (C, Java) or other
discrete data types (Pascal, Ada).
◆ The lower bound may be zero (C, Java), one (Fortran), or
chosen by the programmer (Pascal, Ada)

17
Different Types of Arrays

◆ One-dimensional array: only one index is used

◆ Multi-dimensional array: array involving more than one
index
◆ Static array: the compiler determines how memory will
be allocated for the array
◆ Dynamic array: memory allocation takes place during
execution

18
One Dimensional Static Array

◆ Syntax:
• ElementType arrayName [CAPACITY];
• ElementType arrayName [CAPACITY] =
{ initializer_list };
◆ Example in C++:
• int b [5];
• int b [5] = {19, 68, 12, 45, 72};

19
Array Output Function

void display(int array[],int num_values)

{
for (int I = 0; i<num_values; i++)
cout<< array[i] << “ ”;
}

20
List Implemented Using Array

21
Operations On Lists

◆ We’ll consider only few operations and not

all operations on Lists
◆ Let us consider Insert
◆ There are two possibilities:
• Ordered List
• Unordered List

22
Insertion into an Ordered List

23
Insertion in Detail

24
Insertion

25
Deletion

26
Inserting into an unordered array
#include <stdio.h>
int main()
{
int array[100];
int i, n, x, pos=0;

printf("Enter the number of elements in the array: ");

scanf("%d", &n);
printf("Enter the elements \n");

for (i = 0; i < n; i++)

scanf("%d", &array[i]);

printf("Array elements are: \n");

for (i = 0; i < n; i++)
printf("%d ", array[i]);

printf("\nEnter the new element to be inserted: ");

scanf("%d", &x);

27
Inserting into an unordered array
do {
if(pos > n)
printf("Enter value less than %d\n", n);
else
printf("\nEnter the position where element is to be inserted: ");
scanf("%d", &pos);
}while(pos > n);

//shift all elements 1 position forward from the place

//where element needs to be inserted
n=n+1;
for(i = n-1; i >= pos; i--)
array[i]=array[i-1];

array[pos-1]=x; //Insert the element x on the specified position

//print the new array

printf("The array after insertion\n");
for (i = 0; i < n; i++)
printf("%d ", array[i]);

return 0;
} 28
Find / Search
◆ Searching is the process of looking for a
specific element in an array
◆ For example, discovering whether a
certain score is included in a list of
scores.
◆ Searching, like sorting, is a common task
in computer programming.
◆ There are many algorithms and data
structures devoted to searching.
◆ The most common one is the linear search.

29
Linear Search

◆ The linear search approach compares the

given value with each element in the array.
◆ The method continues to do so until the
given value matches an element in the list
or the list is exhausted without a match
being found.
◆ If a match is made, the linear search
returns the index of the element in the
array that matches the key.
◆ If no match is found, the search returns -1.

30
Linear Search

31
Linear Search Function

int LinearSearch (int a[], int n, int key)

{
int i;
for(i=0; i<n; i++)
{
if (a[i] == key)
return i;
}
return -1;
}

32
Using the Function

◆ LinearSearch (a,n,item,loc)
◆ Here "a" is an array of the size n.
◆ This algorithm finds the location of the element "item"
in the array "a".
◆ If search item is found, it sets loc to the index of the
element; otherwise, it sets loc to -1
◆ index=linearsearch(array, num, key)

33
PrintList Operation

int myArray [5] = {19,68,12,45,72};

/* To print all the elements of the array
for (int i=0;i<5;i++)
{
printf("%d", myArray[i]);
}

34
35
Implementing Deletion

36
Deleting using index
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int i, n, index, arr[10];
printf("Enter the size of the array: ");
scanf("%d", &n);
printf("Enter the elements of the array: \n");
for (i = 0; i < n; i++)
{
printf("arr[%d] = ", i);
scanf("%d", &arr[i]);
}
printf("Enter the index of the element to be deleted: ");
scanf("%d", &index);
if (index >= n+1)
{
printf (" \n Deletion is not possible for the index.");
}
else
{
for (i = index; i < n - 1; i++)
arr[i] = arr[i + 1];
printf("The array after deleting the element is: ");
for (i = 0; i < n - 1; i++)
printf("%d ", arr[i]);
}
printf("\n");
return 0; 37
}
Deletion - Another Method

38
Operations Running Times
PrintList O(N)
Find

Insert O(N) (on avarage half

Delete needs to be moved)

FindKth
Next O(1)
Previous

39
Disadvantages of Using Arrays

◆ Need to define a size for array

• High overestimate (waste of space)
◆ Insertion and deletion is very slow
• need to move elements of the list
◆ Redundant memory space
• it is difficult to estimate the size of array

40
Linked List
◆ Series of nodes
• not adjacent in memory
• contain the element and a pointer to a node containing
its succesor
◆ Avoids the linear cost of insertion and deletion!

41
Singly Linked List

42
Doubly Linked List

43
Singly Linked List

44
Singly-linked List - Addition

◆ Insertion into a singly-linked list has two special cases.

◆ It's insertion a new node before the head (to the very
beginning of the list) and after the tail (to the very end of
the list).
◆ In any other case, new node is inserted in the middle of
the list and so, has a predecessor and successor in the list.

45
Empty list case
◆ When list is empty, which
is indicated by (head ==
NULL) condition, the
insertion is quite simple.
◆ Algorithm sets both head
and tail to point to the new
node.

46
Add first
◆ In this case, new node is inserted right before the current
head node.

47
Add First - Step 1
◆ It can be done in two steps:
• Update the next link of the new node, to point to the current
head node.

48
Add First - Step 2

• Update head link to point to the new node.

49
50
Insertion at the head of a Singly Linked List

To perform this operation, we need to follow two important

conditions. They’re

1. If the list is empty, then the newly created node will be

the head node, and the next node of the head will be ”
NULL”.
2. If the list is not empty, the new node will be the head
node, and the next will point to the previous head node.

function insertAtHead( head, value ):

newNode = Node(value)
if head is NULL:
head = newNode
return head
else:
[Link] = head
return newNode 51
Add last

◆ In this case, new node is inserted right after the current

tail node.

◆ It can be done in two steps:

• Update the next link of the current tail node, to point to the new
node.
• Update tail link to point to the new node.

52
53
Insertion at the end of a Singly Linked List

1. Traverse until the “next” node of the current node becomes null.
2. Create a new node with the speci ed value.

3. Assign the new node as the next node of the tail node.

function insertAtEnd( head, value ):

newNode = Node(value)
if head is NULL:
head = newNode
return head
while [Link] is not NULL:
then head = [Link]
[Link] = newNode
[Link] = NULL
54
fi
Insert - General Case
◆ In general case, new node is always inserted between two
nodes, which are already in the list. Head and tail links
are not updated in this case.
◆ We need to know two nodes "Previous" and "Next",
between which we want to insert the new node.
◆ This also can be done in two steps:
• Update link of the "previous" node, to point to the new node.
• Update link of the new node, to point to the "next" node.

55
function insertAfter( head, value,
searchItem ):
newNode = Node(value)
while [Link] equals searchItem:
then head = [Link]
[Link] = [Link]
[Link] = newNode

56
Singly-linked List - Deletion

◆ There are four cases, which can occur while removing the
node.
◆ We have the same four situations, but the order of
algorithm actions is opposite.
◆ Notice, that removal algorithm includes the disposal of
the deleted node - unnecessary in languages with
automatic garbage collection (Java).

57
List has only one node
◆ When list has only one
node, that the head points
to the same node as the
tail, the removal is quite
simple.
◆ Algorithm disposes the
node, pointed by head (or
tail) and sets both head
and tail to NULL.

58
Remove First

◆ In this case, first node (current head node) is removed

from the list.
◆ It can be done in two steps:
• Update head link to point to the node, next to the head.
• Dispose removed node.

function deleteHead( head ):

temp = head
head = [Link]
free( temp )
return head

59
60
Remove Last
◆ In this case, last node (current tail node) is removed from
the list. This operation is a bit more tricky, than removing
the first node, because algorithm should find a node,
which is previous to the tail first.
◆ It can be done in three steps:
• Traverse before the tail node. Save the current node
• Free the memory of the next node of the current node.
• Set the next node of the current node as NULL.

function deleteTail( head ):

while [Link] is not NULL:
head = [Link]
free( [Link] )
[Link] = NULL

61
62
Remove - General Case

◆ In general case, node to be removed is always located

between two list nodes. Head and tail links are not
updated in this case.
◆ We need to know two nodes "Previous" and "Next", of
the node which we want to delete.
◆ Such a removal can be done in two steps:
• Update next link of the previous node, to point to the next node,
relative to the removed node.
• Dispose removed node.

63
64
 function searchAndDelete( head, searchItem ):
while [Link] is not NULL and [Link] is not equals
searchItem :
head = [Link]
[Link] = [Link]
delete([Link])

Advantages of Using Linked Lists

◆ Need to know where the first node is
• the rest of the nodes can be accessed
◆ No need to move the elements in the list for
insertion and deletion operations
◆ No memory waste
65
Cursor Implementation

Problems with linked list implementation:

◆ Same language do not support pointers!
• Then how can you use linked lists ?
◆ new and free operations are slow
• Actually not constant time
◆ SOLUTION: Implement linked list on an array - called
CURSOR

66
Cursor Implementation - Diagram

67
Cursor Implementation

If L = 5, then L represents list (A, B, E)

If M = 3, then M represents list (C, D, F)

68
Arrays - Pros and Cons

◆ Pros
• Directly supported by C
• Provides random access
◆ Cons
• Size determined at compile time
• Inserting and deleting elements is time
consuming

69
Linked Lists - Pros and Cons

◆ Pros
• Size determined during runtime
• Inserting and deleting elements is quick
◆ Cons
• No random access
• User must provide programming support

70
Application of Lists

◆ Lists can be used

◆ To store the records sequentially
◆ For creation of stacks and queues
◆ For polynomial handling
◆ To maintain the sequence of operations for do /
undo in software
◆ To keep track of the history of web sites visited

71
Why Doubly Linked List ?

◆ given only the pointer location, we cannot access its predecessor in

the list.
◆ Another task that is difficult to perform on a linear linked list is
traversing the list in reverse.
◆ Doubly linked list A linked list in which each node is linked to both
its successor and its predecessor
◆ In such a case, where we need to access the node that precedes a
given node, a doubly linked list is useful.

72
Doubly Linked List

◆ In a doubly linked list, the nodes are linked in both

directions. Each node of a doubly linked list contains
three parts:
• Info: the data stored in the node
• Next: the pointer to the following node
• Back: the pointer to the preceding node

73
Operations on Doubly Linked Lists

◆ The algorithms for the insertion and deletion operations

on a doubly linked list are somewhat more complicated
than the corresponding operations on a singly linked list.
◆ The reason is clear: There are more pointers to keep track
of in a doubly linked list.

74
Inserting Item

◆ As an example, consider the Inserting an item.

◆ To link the new node, after a given node, in a singly
linked list, we need to change two pointers:
• newNode->next and
• location->next.
◆ The same operation on a doubly linked list requires four
pointer changes.

75
Singly Linked List Insertion

76
Doubly Linked List Insertion

77
The Order is Important

78
function insertAtFront (ListHead, value):
newNode = Node()
[Link] = value
[Link] = NewNode
[Link] = ListHead
[Link] = NULL
return ListHead
function insertAtTail(ListHead, value):
newNode = Node()
[Link] = value
[Link] = NULL
while [Link] is not NULL:
then ListHead = [Link]
[Link] = ListHead
[Link] = newNode
return ListHead

function insertAfter(ListHead, searchItem, value):

List = ListHead
NewNode = Node()
[Link] = value
while [Link] is not equal searchItem
then List = [Link]
List = [Link]
[Link] = [Link]
[Link] = List
[Link] = NewNode
79
Doubly Linked List - Deletion

◆ One useful feature of a doubly linked list is its

elimination of the need for a pointer to a node's
predecessor to delete the node.
◆ Through the back member, we can alter the next member
of the preceding node to make it jump over the unwanted
node.
◆ Then we make the back pointer of the succeeding node
point to the preceding node.

80
Doubly Linked List - Deletion

81
function deleteHead(ListHead):
PrevHead = ListHead
ListHead = [Link]
[Link] = NULL
[Link] = NULL
free memory(PrevHead)
return ListHead function DeleteTail( ListHead ):
head = ListHead
while [Link] is not NULL:
ListHead = [Link]
Tail = [Link]
[Link] = NULL
free memory( Tail )
return head

function SearchAndDelete(ListHead, searchItem):

head = ListHead
while [Link] not equals searchItem:
head = [Link]
deleteNode = [Link]
[Link] = [Link]
[Link] = head
[Link], [Link] = NULL
free memory(deleteNode)
return ListHead
82
Special Cases of Deletion

◆ We do, however, have to be careful about the end cases:

• If location->back is NULL, we are deleting the first node
• if location->next is NULL, we are deleting the last node.
• If both location->back and location->next are NULL, we are
deleting the only node.

83