Lineary data structures
Data Structures and Algorithms
DSaA 2012/2013
Lineary data structures
Lineary data structures:
" stacks
" queues
" lists
 unordered singly-linked list
 ordered doubly-linked list
DSaA 2012/2013
Stack
Stack is an abstract data structure, in which an element can be inserted and removed only on one end. Stack is a
LIFO structure (last in, first out), it means last inserted element will be the first removed element.
Basic operations on a stack:
Init(stack)  empties, or preparing the structure to work
Empty(stack)  return true if the stack is empty
Full(stack) - return true if the stack is full
Push(el, stack)  push an element on the top of the stack
Pop(stack)  pop an element from the top of the stack
push 6 push 9 pop push 1 push 7 pop pop push 8
7
9 1 1 1 8
6 6 6 6 6 6 6 6
operation sequence on a stack
DSaA 2012/2013
Stack - realizations
Different representations of a stack in computer (program)
- an array with one organizing index
- limited capacity
- better for one-type stack
- a list
-  unlimited capacity
- different type of element can be used
Stack realized as an array
Top of stack=6
8 1 5 7 4 2
0 1 2 3 4 5 6
DSaA 2012/2013
Stack (an array)
typedef struct{
int *arr;
int size;
int top;
bool push(Stack &stack, int elem)
} Stack;
{
if(full(stack))
void init(Stack &stack, int
return false;
size)
stack.arr[stack.top++]=elem;
{
return true;
stack.top=0;
}
stack.arr=new int[size];
stack.size=size;
bool pop(Stack &stack, int &elem)
}
{
if(empty(stack))
bool empty(Stack stack)
return false;
{
elem=stack.arr[--stack.top];
return stack.top==0;
return true;
}
}
bool full(Stack stack)
{
return stack.top==stack.size;
}
DSaA 2012/2013
Queue
Queue is a structure for waiting persons, in which someone can come and stand on the end and someone from the
front can go through. Queue is a FIFO structure (first in, first out), it means last inserted element will be the last
taken element.
Basic operations on a queue:
Init(queue) - empties, or preparing the structure to work
Empty(queue) - return true if the queue is empty
Full(queue) - return true if the queue is full
Enqueue(el, queue)  add an element to the queue
Dequeue(queue)  return and delete the first element from the queue
Enqueue 6
Dequeue
9 1 7
Enqueue 9
6
Dequeue
1 7
Dequeue
6 9
Enqueue 8
7
Enqueue 1
9
7 8
Enqueue 7
9 1
DSaA 2012/2013
Queue - realizations
Queue representations in computer programs
- an array with one organization index
- similar to stack representation with elements shift
- an array with two organization indexes
- with  empty position
- without  empty position
- a list
End of queue=6
Begin of queue=0
8 1 5 7 4 2
0 1 2 3 4 5 6
Empty queue Full queue
Begin = x End = x Begin = x End = x
3 6 2 9 1 6
0 1 2 3 4 5 0 1 2 3 4 5
DSaA 2012/2013
Queue (array with  empty position)
Empty queue
Begin = 2 End = 2
0 1 2 3 4 5
Queue
Begin = 1 End = 5 End = 2 Begin = 4
1 5 7 4 8 1 4 2
0 1 2 3 4 5 0 1 2 3 4 5
Full queue
End = 5
End = 3 Begin = 4 Begin = 0
8 1 5 4 2 8 1 5 7 4
0 1 2 3 4 5 0 1 2 3 4 5
DSaA 2012/2013
Queue(cont.)  enqueue, dequeue
Enqueue(3)
E = 2 B = 4 B = 1 E = 3 B = 2 E = 5
8 1 4 3 1 5 5 7 4
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
E = 3 B = 4 B = 1 E = 4 E = 0 B = 2
8 1 3 4 3 1 5 3 5 7 4 3
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
a) b) c)
Dequeue
B = 1 E = 4
E = 2 B = 3 E = 2 B = 5
8 1 3 4 7 8 1 4
1 5 3
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
B = 0 E = 2
B = 2 E = 4 E = 2 B = 4
5 3 8 1 4 7 8 1
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
DSaA 2012/2013
Queue (an array)
typedef struct
bool enqueue(Queue &queue, int elem)
{
{
int *arr;
if(full(queue))
int size;
return false;
int begin;
queue.arr[queue.end++]=elem;
int end;
if(queue.end>=queue.size)
} Queue;
queue.end=0;
return true;
void init(Queue &queue, int size)
}
{
queue.begin=0;
bool dequeue(Queue &queue, int &elem)
queue.end=0;
{
queue.arr=new int[size+1];
if(empty(queue))
queue.size=size+1;
return false;
}
elem=queue.arr[queue.begin++];
bool empty(Queue queue)
if(queue.begin>=queue.size)
{
queue.begin=0;
return queue.begin==queue.end;
return true;
}
}
bool full(Queue queue)
{
return (queue.begin==0 && queue.end==queue.size-1)
|| (queue.begin==queue.end+1);
}
DSaA 2012/2013
Linked List
A linked list is a data structure in which the objects are arranged in a
linear order. The order in a linked list is determined by a reference
(pointer) in each object
An element of a linked list is implemented as a record type and have to have
minimum two fields: a key and a reference to a next element. If an element do
not have a predecessor, it is called a head. If an element does not have a
successor, it is called a tail.
null
Different
graphic
representation
head tail
DSaA 2012/2013
Linked List (cont.)
A reference is often an address, under which there is a next element. So we need a reference to the first
element of list to have an access to any element. This reference is often stored in a variable called head.
If head=null then the list is empty.
head
empty list
head
5 one-element list
head
5 2 7 20 four-element list
DSaA 2012/2013
Linked List  insertAsHead
An element of a list can have some additional dates besides a key. But for simplification only a key will be used.
newEl head key
After {9} ?
5
1 typedef struct TagElemLL
newEl head key
2 {
After {11}
5
3 int key;
4 TagElemLL *next;
?
5 } ElemLL;
?
6
7 typedef ElemLL *LinkedList;
newEl
head key
8 After {12}
5
9 void insertAsHead(LinkedList &head, int key)
10 {
5
11 ElemLL *newEl=new ElemLL;
?
12 newEl->key=key;
newEl
13 newEl->next=head; head key
After {13}
14 head=newEl;
5
15 }
5
newEl
head key
After {14}
5
5
DSaA 2012/2013
Linked List  insertAsHead (cont.)
key
key
1
8
head
newEl
head
newEl
After {12}
After {12}
5
8
4
1 8 5
?
?
head
newEl
head
newEl
8
After {13} 5
1
4
8 5
After {13}
head
newEl
head newEl
8
5
1
4
After {14} 8 5
After {14}
DSaA 2012/2013
Linked List  findElem
p
key key
head
ElemLL *findElem(
8 7
1 4 8 5
LinkedList head, int key)
{
ElemLL *p=head;
p
while(p!=null && p->key!=key)
p=p->next;
key key
return p; head
8 7
1 4 8 5
}
p
key key
head
8 7
1 4 8 5
p
key
head
7
1 4 8 5
p
key
head
7
1 4 8 5
DSaA 2012/2013
Linked list  removeHead
void removeHead(LinkedList &head)
{
if(head!=null)
head head
{
ElemLL *p=head;
p p
head=head->next;
1 4 8 5 5
delete p;
}
}
head head
p p
1 4 8 5 5
head head
p p
4 8 5
? ?
DSaA 2012/2013
Linked list - removeElem
head p x
Element to remove
Before removing
1 4 8 7 5
....
....
head p x
Changes
1 4 8 7 5
....
in predecessor
....
head p x
?
Removing
1 4 7 5
....
from memory
....
head
After removing
1 4 7 5
....
....
DSaA 2012/2013
Linked list - removeElem
void removeElem(LinkedList &head, int key)
{
if(head!=null)
if(head->key==key)
removeHead(head);
else
{
ElemLL *p=head,*x;
while(p->next!=null && p->next->key!=key)
p=p->next;
if(p->next->key==key) // WRONG !!!
{
x=p->next;
p->next=x->next;
delete x;
}
}
}
DSaA 2012/2013
Linked list as a stack or a queue
" Linked list with a head (one organising reference) is
suitable for stack implementation. Pushing on stack is
realised by inserting as a head and popping an element
 as removing a head. Such a stack is of unlimited
capacity.
" Linked list can be used also for queue implementation.
but because of optimisation besides of head we need a
pointer to a tail.
head = begin of a queue tail = end of a queue
5 2 7 20
DSaA 2012/2013
Linked list  insertAsTail
typedef struct
head tail newEl
{
key
ElemLL *head,*tail;
1
} LinkedList;
4 8 5 1
void insertAsTail(LinkedList &list, int key)
{
head tail newEl
ElemLL *newEl=new ElemLL;
newEl->key=key;
newEl->next=null;
4 8 5 1
if(list.tail!=null)
list.tail->next=newEl;
else
head tail newEl
list.head=newEl;
list.tail=newEl;
}
4 8 5 1
DSaA 2012/2013
Double linked list
An element of doubly-linked list (two-way linked list) has two pointers. The first is an address for
successor, the second  for predecessor. As singly-linked list (one-way linked list), double linked list can
have one or two one organising pointers.
head
tail
head tail
head tail
one-element list
empty list
Let s consider a double linked list ordered by a key. The searching for element with specific key is similar as for
single linked list. But the inserting and removing procedure are different.
DSaA 2012/2013
Double linked list - insertElem
During inserting a new element into sorted list we have to consider 4 situation: Inserting:
- into an empty list
- as a head
- in the middle of the list (after a head and before a tail)
- as a tail
as a head
1) 3)
newEl head tail newEl tail
head
1 3 5 8
1 3 5 8
?
newEl head newEl
tail head tail
2) 4)
1 3 5 8
1 3 5 8
DSaA 2012/2013
Double linked list  insertElem &
in the middle
4
1) 3)
head newEl p tail
head newEl p tail
?
1 3 5 8
1 3 4 5 8
head newEl p tail
head newEl p tail
2) 4)
1 3 4 5 8
1 3 4 5 8
?
?
DSaA 2012/2013
Double linked list  insertElem &
as a tail
1) 3)
head tail newEl head tail newEl
?
3 5 8 3 5 8 9
head tail newEl
2) 4)
head tail newEl
3 5 8 9
3 5 8
? 9
DSaA 2012/2013
Double linked list  insertElem &
void insert(DoubledLinkedList list, int key)
typedef struct TagElemLL
{
{
ElemLL *newEl=new ElemLL;
int key;
newEl->key=key;
TagElemLL *next,*prev;
ElemLL *p=list.head;
} ElemLL;
while(p!=null && p->key p=p->next;
typedef struct
if(p==null)
{
{
ElemLL *head,*tail;
newEl->next=null;
} DoubledLinkedList;
newEl->prev=list.tail;
if(list.tail!=null)
list.tail->next=newEl;
else
list.head=newEl;
list.tail=newEl;
}
else
{
newEl->next=p;
newEl->prev=p->prev;
p->prev=newEl;
if(newEl->prev==null)
list.head=newEl;
else
newEl->prev->next=newEl;
}
}
DSaA 2012/2013
List - operation
" Basic operations:
 insert as head
 insert as tail
 insert in order (for ordered list)
 remove head
 remove tail
 remove chosen
 show/compute something for all
 find
 count
 remove all
" Other operation:
 merge lists
 reverse list
 copy list
 &
DSaA 2012/2013
List category
" List link:
 singly-linked  one-way linked
 doubly-linked  two-way linked
" List order:
 ordered
 unordered
tail
" List inner organisation:
 with head or tail
 with head and tail
5 2 7 20
" List end:
 ordinary-linked
 circularly-linked
" Specific lists:
 with sentinel
 cycled on last element
DSaA 2012/2013
Advances, disadvances
" list vs arrar
 list:
" dynamic(+)
" unlimited(+)
" sequential access(-)
" extra storage(-),
 array:
" static(-)
" limited(-)
" random access(+)
DSaA 2012/2013