Data Structures and Algorithms

Linked Lists, Stacks and Queues

 Data Structure
• A construct that can be defined within a
programming language to store a
collection of data
– one may store some data in an array of
integers, an array of objects, or an array of
arrays
 Abstract Data Type (ADT)

• Definition: a collection of data together

with a set of operations on that data
– specifications indicate what ADT
operations do, but not how to implement
them
– data structures are part of an ADT’s
implementation
• Programmer can use an ADT without
knowing its implementation.
 Typical Operations on Data
• Add data to a data collection
• Remove data from a data collection
• Ask questions about the data in a data
collection. E.g., what is the value at a
particular location, and is x in the
collection?
 Why ADT
• Hide the unnecessary details
• Help manage software complexity
• Easier software maintenance
• Functionalities are less likely to change
• Localised rather than global changes

CS 201
 Illustration

CS 201
Linked Lists
 Lists
• List: a finite sequence of data items
a1, a2, a3, …, an
• Lists are pervasive in computing
– e.g. class list, list of chars, list of events
• Typical operations:
– Creation
– Insert / remove an element
– Test for emptiness
– Find an item/element
– Current element / next / previous
– Find k-th element
– Print the entire list
 Array-Based List Implementation
• One simple implementation is to use arrays
– A sequence of n-elements
• Maximum size is anticipated a priori.
• Internal variables:
– Maximum size maxSize (m)
– Current size curSize (n)
– Current index cur
– Array of elements listArray
listArray cur
curSize

n a1 a2 a3 an unused

0 1 2 n-1 m
 Inserting Into an Array

• While retrieval is very fast, insertion and

deletion are very slow
– Insert has to shift upwards to create gap
Example : insert(2, it, arr)
Size arr

8 a1 a2 a3 a4 a5 a6 a7 a8

Step 2 : Write into gap

Size
Step 1 : Shift upwards
arr

9
8 a1 a2 it a3 a4 a5 a6 a7 a8

Step 3 : Update Size

 Coding
typedef struct {
int arr[MAX];
int max;
int size;
} LIST

void insert(int j, int it, LIST *pl)

{ // pre : 1<=j<=size+1
int i;
for (i=pl->size; i>=j; i=i-1)
// Step 1: Create gap
{ pl->arr[i+1]= pl->arr[i]; };
pl->arr[j]= it; // Step 2: Write to gap
pl->size = pl->size + 1; // Step 3: Update size
}
 Deleting from an Array
• Delete has to shift downwards to close gap of
deleted item
Example: deleteItem(4, arr)
size arr

9 a1 a2 it a3 a4 a5 a6 a7 a8

Step 1 : Close Gap

size arr

98 a1 a2 it a3 a5 a6 a7 a8 a8

Step 2 : Update Size

Not part of list
 Coding

void delete(int j, LIST *pl)

{ // pre :
1<=j<=size
for (i=j+1; i<=pl->size; i=i+1)
// Step1: Close gap
{ pl->arr[i-i]=pl->arr[i]; };
// Step 2: Update size
pl->size = pl->size - 1;
}
 Linked List Approach
• Main problem of array is the slow deletion/insertion since it
has to shift items in its contiguous memory
• Solution: linked list where items need not be contiguous
with nodes of the form item next
ai

• Sequence (list) of four items < a1,a2 ,a3 ,a4 > can be
represented by:
head represents
null

a1 a2 a3 a4
 Pointer-Based Linked Lists

• A node in a linked list is usually a struct

struct Node
{ int item A node

Node *next;
}; //end struct
• A node is dynamically allocated
Node *p;
p = malloc(sizeof(Node));
 Pointer-Based Linked Lists
• The head pointer points to the first node in
a linked list
• If head is NULL, the linked list is empty
– head=NULL
• head=malloc(sizeof(Node))
A Sample Linked List
 Traverse a Linked List
• Reference a node member with the ->
operator
p->item;
• A traverse operation visits each node in
the linked list
– A pointer variable cur keeps track of the
current node
for (Node *cur = head;
cur != NULL;
cur = cur->next)
x = cur->item;
 Traverse a Linked List

The effect of the assignment cur = cur->next

CS 201
 Delete a Node from a Linked List
• Deleting an interior/last node
prev->next=cur->next;
• Deleting the first node
head=head->next;
• Return deleted node to system
cur->next = NULL;
free(cur);
cur=NULL;
 Delete a Node from a Linked List

Deleting a node from a linked list

Deleting the first node

 Insert a Node into a Linked List
To insert a node between two nodes
newPtr->next = cur;
prev->next = newPtr;

Inserting a new node

into a linked list
 Insert a Node into a Linked List
To insert a node at the beginning of a linked
list
newPtr->next = head;
head = newPtr;

Inserting at the beginning

of a linked list
 Insert a Node into a Linked List
Inserting at the end of a linked list is not a
special case if cur is NULL
newPtr->next = cur;
prev->next = newPtr;

Inserting at the end of a

linked list
 Look up

BOOLEAN lookup (int x, Node *L)

{ if (L == NULL)
return FALSE
else if (x == L->item)
return TRUE
else
return lookup(x, L-next);
}
 An ADT Interface for List
• Functions • Data Members
– isEmpty – head
– getLength – Size
– insert • Local variables to
– delete member functions
– Lookup – cur
–… – prev
 Doubly Liked Lists
• Frequently, we need to traverse a sequence
in BOTH directions efficiently
• Solution : Use doubly-linked list where each
node has two pointers
forward traversal

Doubly Linked List. next

head x1 x2 x4
x3
prev

backward traversal
 Circular Linked Lists
• May need to cycle through a list repeatedly,
e.g. round robin system for a shared resource

• Solution : Have the last node point to the first

node
Circular Linked List.
head x1 x2 ... xn
Stacks
 What is a Stack?
• A stack is a list with the restriction that
insertions and deletions can be performed in
only one position, namely, the end of the list,
called the top.
• The operations: push (insert) and pop (delete)
pop push(o)

Top 3
2
7
6
 Stack ADT Interface

• The main functions in the Stack ADT are (S is the stack)

boolean isEmpty(); // return true if empty

boolean isFull(S); // return true if full

void push(S, item); // insert item into stack

void pop(S); // remove most recent item

void clear(S); // remove all items from stack

Item top(S); // retrieve most recent item

Item topAndPop(S); // return & remove most recent item

 Sample Operation
Stack S = malloc(sizeof(stack));

push(S, “a”);

push(S, “b”);

push(S, “c”); s

d=top(S); d
top
pop(S);

e
push(S, “e”);

c
pop(S);

b
a
 Implementation by Linked Lists
• Can use a Linked List as implementation of stack

StackLL

lst Top of Stack = Front of Linked-List

LinkedListItr

head

a1 a2 a3 a4
 Code

struct Node {
int element;
Node * next;
};
typedef struct Node * STACK;
More code
More Code
 Implementation by Array
• use Array with a top index pointer as an implementation of stack

StackAr

arr

0 1 3 4 6 7 8 9
2 5

A A B C D E F

top
Code
More code
More code
Effects
 Applications
• Many application areas use stacks:
– line editing
– bracket matching
– postfix calculation
– function call stack
Queues
 What is a Queue?
• Like stacks, queues are lists. With a queue,
however, insertion is done at one end whereas
deletion is done at the other end.
• Queues implement the FIFO (first-in first-out)
policy. E.g., a printer/job queue!
• Two basic operations of queues:
– dequeue: remove an item/element from front
– enqueue: add an item/element at the back

dequeue enqueue
 Queue ADT
• Queues implement the FIFO (first-in first-out) policy
– An example is the printer/job queue!

enqueue(o)
dequeue()

isEmpty()
getFront() createQueue()
 Sample Operation

Queue *Q;

enqueue(Q, “a”); q
enqueue(Q, “b”);

enqueue(Q, “c”);
d
d=getFront(Q);
front back
dequeue(Q);
a b c e
enqueue(Q, “e”);

dequeue(Q);
 Queue ADT interface
• The main functions in the Queue ADT are (Q is the
queue)
void enqueue(o, Q) // insert o to back of Q

void dequeue(Q); // remove oldest item

Item getFront(Q); // retrieve oldest item

boolean isEmpty(Q); // checks if Q is empty

boolean isFull(Q); // checks if Q is full

void clear(Q); // make Q empty

}
 Implementation of Queue (Linked
List)
• Can use LinkedListItr as underlying implementation of Queues

Queue

lst

addTail
LinkedList

head tail

a1 a2 a3 a4
 Code

struct Node {
int element;
Node * next;
};

struct QUEUE {
Node * front;
Node * rear;
};
More code
 More code

CELL is a list node