List Data Structure, Linked List, Stacks.ppt

List Data Structures

1. Data Structures
Linked Lists, Stacks and Queues

2. 09/02/24 CS 201
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

3. 09/02/24 CS 201
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.

4. 09/02/24 CS 201
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?

5. 09/02/24 CS 201
Why ADT
•Hide the unnecessary details
•Help manage software complexity
•Easier software maintenance
•Functionalities are less likely to change
•Localised rather than global changes

6. 09/02/24 CS 201
Illustration

7. Linked Lists

8. 09/02/24 CS 201
Lists
•List: a finite sequence of data items
a1, a2, a3, …, an
•A list is an ordered data structure
•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

9. 09/02/24 CS 201
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
n
curSize
a
1
a
2a
3 a
n
listArray
unused
012 n-1 m
cur

10. 09/02/24 CS 201
Inserting Into an Array
•While retrieval is very fast, insertion and
deletion are very slow
– Insert has to shift upwards to create gap
a
1a
2 a
7a
8
a
4a
5a
6
a
3
Step 1 : Shift upwards
8
Size arr
8 a
1a
2a
3 a
7a
8
Size arr
a
4a
5a
6
Example : insert(2, it, arr)
Step 2 : Write into gap
it
Step 3 : Update Size
9

11. 09/02/24 CS 201
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
}

12. 09/02/24 CS 201
Deleting from an Array
•Delete has to shift downwards to close gap of
deleted item
Step 1 : Close Gap
9 a
1a
2it a
7
a
8
size
a
5a
6a
3
a
8
arr
9 a
1a
2it a
7a
8
size
a
4a
5a
6a
3
arr
Example: deleteItem(4, arr)
Step 2 : Update Size
8
Not part of list

13. 09/02/24 CS 201
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;
}

14. 09/02/24 CS 201
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
•Sequence (list) of four items < a
1
,a
2
,a
3
,a
4
> can be
represented by:
item next
a
i
a
1 a
2 a
3 a
4
head represents
null

15. Pointer-Based Linked Lists
•A node in a linked list is usually a struct
struct Node
{ int item
Node *next;
}; //end struct
•A node is dynamically allocated
Node *p;
p = malloc(sizeof(Node));
A node
09/02/24 CS 201

16. 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))
09/02/24 CS 201

17. A Sample Linked List
09/02/24 CS 201

18. 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;
09/02/24 CS 201

19. Traverse a Linked List
The effect of the assignment cur = cur->next
09/02/24 CS 201

20. 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;
09/02/24 CS 201

21. Delete a Node from a Linked List
Deleting a node from a linked list
Deleting the first node
09/02/24 CS 201

22. 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
CS 201

23. 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
CS 201

24. 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
CS 201

25. 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);
}
09/02/24 CS 201

26. An ADT Interface for List
•Functions
–isEmpty
–getLength
–insert
–delete
–Lookup
–…
•Data Members
–head
–Size
•Local variables to
member functions
–cur
–prev
09/02/24 CS 201

27. 09/02/24 CS 201
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
next
forward traversal
Doubly Linked List.
x
1 x
4x
2
head
x
3
backward traversal
prev

28. 09/02/24 CS 201
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
x
1 x
2 x
n. . .
Circular Linked List.
head

29. Stacks

30. 09/02/24 CS 201
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)
6
7
2
3Top

31. 09/02/24 CS 201
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

32. 09/02/24 CS 201
Sample Operation
Stack S = malloc(sizeof(stack));
push(S, “a”);
push(S, “b”);
push(S, “c”);
d=top(S);
pop(S);
push(S, “e”);
pop(S);
s
a
b
c
top
e
d

33. 09/02/24 CS 201
Implementation by Linked Lists
•Can use a Linked List as implementation of stack
Top of Stack = Front of Linked-List
StackLL
lst
a
1 a
2 a
3 a
4
head
LinkedListItr

34. 09/02/24 CS 201
Code
struct Node {
int element;
Node * next;
};
typedef struct Node * STACK;

35. 09/02/24 CS 201
More code

36. More Code
09/02/24 CS 201

37. 09/02/24 CS 201
Implementation by Array
•use Array with a top index pointer as an implementation of stack
EF
0 1 7 8 923 4 5 6
ABCD
top
StackAr
arr
A

38. 09/02/24 CS 201
Code

39. 09/02/24 CS 201
More code

40. 09/02/24 CS 201
More code

41. Effects
09/02/24 CS 201

42. 09/02/24 CS 201
Applications
•Many application areas use stacks:
–line editing
–bracket matching
–postfix calculation
–function call stack

43. 09/02/24 CS 201
Line Editing
•A line editor would place characters read into a
buffer but may use a backspace symbol (denoted by
) to do error correction
•Refined Task
–read in a line
–correct the errors via backspace
–print the corrected line in reverse
Input :
Corrected Input :
Reversed Output :
abc_defgh2klpqrwxyz
abc_defg2klpwxyz
zyxwplk2gfed_cba

44. 09/02/24 CS 201
The Procedure
•Initialize a new stack
•For each character read:
–if it is a backspace, pop out last char
entered
–if not a backspace, push the char into
stack
•To print in reverse, pop out each char
for output
Input : fghryz
Corrected Input :
Reversed Output :
fyz
zyf Stack
f
g
hr
y
z

45. 09/02/24 CS 201
Bracket Matching Problem
•Ensures that pairs of brackets are properly matched
• An Example:{a,(b+f[4])*3,d+f[5]}
• Bad Examples:
(..)..) // too many closing brackets
(..(..) // too many open brackets
[..(..]..) // mismatched brackets

46. 09/02/24 CS 201
Informal Procedure
Initialize the stack to empty
For every char read
if open bracket then push onto stack
if close bracket, then
return & remove most recent item
from the stack
if doesn’t match then flag error
if non-bracket, skip the char read
Example
{a,(b+f[4])*3,d+f[5]}

Stack
{
(
[
)
}
]
[]

47. 09/02/24 CS 201
Postfix Calculator
•Computation of arithmetic expressions can be efficiently
carried out in Postfix notation with the help of a stack.
Infix - arg1 op arg2
Prefix - op arg1 arg2
Postfix - arg1 arg2 op
(2*3)+4
2*(3+4) 2 3 4 + *
2*3+4
infix
2 3 * 4 +
postfix

48. 09/02/24 CS 201
Informal Procedure
Initialise stack S
For each item read.
If it is an operand,
push on the stack
If it is an operator,
pop arguments from stack;
perform operation;
push result onto the stack
2
3
4
Stack
Expr
2
3
4
+
*
push(S, 2)
push(S, 3)
push(S, 4)
arg2=topAndPop(S)
arg1=topAndPop(S)
push(S, arg1+arg2)
arg2=topAndPop(S)
arg1=topAndPop(S)
push(S, arg1*arg2)
3+4=7
2*7=14

49. 09/02/24 CS 201
Summary
•The ADT stack operations have a last-
in, first-out (LIFO) behavior
•Stack has many applications
–algorithms that operate on algebraic
expressions
–a strong relationship between recursion
and stacks exists
•Stack can be implemented using arrays
or linked lists

50. Queues

51. 09/02/24 CS 201
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

52. 09/02/24 CS 201
Queue ADT
•Queues implement the FIFO (first-in first-out)
policy
–An example is the printer/job queue!
enqueue(o)
dequeue()
isEmpty()
getFront() createQueue()

53. 09/02/24 CS 201
Sample Operation
Queue *Q;
enqueue(Q, “a”);
enqueue(Q, “b”);
enqueue(Q, “c”);
d=getFront(Q);
dequeue(Q);
enqueue(Q, “e”);
dequeue(Q);
q
front back
abce
d

54. 09/02/24 CS 201
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

}

55. 09/02/24 CS 201
Implementation of Queue
(Linked List)
•Can use LinkedListItr as underlying implementation of Queues
a
1 a
2 a
3 a
4
head
tail
Queue
lst
LinkedList
addTail

56. 09/02/24 CS 201
Code
struct Node {
int element;
Node * next;
};
struct QUEUE {
Node * front;
Node * rear;
};

57. 09/02/24 CS 201
More code

58. More code
09/02/24 CS 201
CELL is a list node

59. 09/02/24 CS 201
Implementation of Queue
(Array)
•use Array with front and back pointers as implementation of
queue
Queue
arr
0 1 7 8 923 4 5 6
ABCDEFG
front
back

60. 09/02/24 CS 201
Circular Array
•To implement queue, it is best to view arrays as circular structure
0 1 7 8 923 4 5 6
ABCDEFG
front
back
front
back
A
B
C
D
EF
G
0
1
7
8
9
2
3
4
5
6
Circular view of arrays.

61. 09/02/24 CS 201
How to Advance
•Both front & back pointers should make advancement until they
reach end of the array. Then, they should re-point to beginning
of the array
front = adv(front);
back = adv(back);
int adv(int p)
{ return ((p+1) % maxsize);
}
Alternatively, use modular arithmetic:
mod operator
int adv(int p)
{ int r = p+1;
if (r<maxsize) return r;
else return 0;
}
upper bound of the array

62. 09/02/24 CS 201
Sample
Queue *Q;
enqueue(Q, “a”);
enqueue(Q, “b”);
enqueue(Q, “c”);
dequeue(Q);
dequeue(Q);
enqueue(Q, “d”);
enqueue(Q, “e”);
dequeue(Q);
a
Q
F=front
B=back
F
B
bcd
F
BBB
FF
BB
e

63. 09/02/24 CS 201
Checking for Full/Empty State
What does (F==B) denote?
F
B
Queue
Empty
State
cde
B
F
f Queue
Full
State
size 0 size 4
cde
BF
Alternative - Leave a Deliberate Gap!
No need for size field.
Full Case : (adv(B)==F)

64. 09/02/24 CS 201
Summary
•The definition of the queue operations
gives the ADT queue first-in, first-out
(FIFO) behavior
•The queue can be implemented by
linked lists or by arrays
•There are many applications
–Printer queues,
–Telecommunication queues,
–Simulations,
–Etc.