DSaA 2012/2013
Lineary data structures
Data Structures and Algorithms
DSaA 2012/2013
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
6
pop
6
9
push 1
6
push 7
6
1
pop
6
1
7
pop
6
1
6
push 8
6
8
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
8
1
5
7
4
2
Top of stack=6
5
4
3
2
1
0
Stack realized as an array
6
DSaA 2012/2013
Stack (an array)
typedef struct{
int *arr;
int size;
int top;
} Stack;
void init(Stack &stack, int
size)
{
stack.top=0;
stack.arr=new int[size];
stack.size=size;
}
bool empty(Stack stack)
{
return stack.top==0;
}
bool full(Stack stack)
{
return stack.top==stack.size;
}
bool push(Stack &stack, int elem)
{
if(full(stack))
return false;
stack.arr[stack.top++]=elem;
return true;
}
bool pop(Stack &stack, int &elem)
{
if(empty(stack))
return false;
elem=stack.arr[--stack.top];
return true;
}
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
Enqueue 9
Dequeue
6
6 9
9
9 1
9 1 7
1 7
7
7 8
Enqueue 1
Enqueue 7
Dequeue
Dequeue
Enqueue 8
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
8
1
5
7
4
2
End of queue=6
5
4
3
2
1
0
6
Begin of queue=0
Begin = x
End = x
Empty queue
5
4
3
2
1
0
Begin = x
End = x
3
6
2
9
1
6
Full queue
5
4
3
2
1
0
DSaA 2012/2013
Queue (array with „empty” position)
Begin = 2
End = 2
8
1
5
4
2
Begin = 4
End = 3
8
1
5
7
4
Begin = 0
End = 5
Empty queue
Full queue
8
1
4
2
Begin = 4
End = 2
1
5
7
4
Queue
End = 5
Begin = 1
5
4
3
2
1
0
5
4
3
2
1
0
5
4
3
2
1
0
5
4
3
2
1
0
5
4
3
2
1
0
DSaA 2012/2013
Queue(cont.)
– enqueue, dequeue
1
5
8
1
4
1
5
3
8
1
3
4
5
7
4
5
7
4
E = 2 B = 4
E = 3 B = 4
Enqueue(3)
a)
c)
B = 1
E = 3
B = 1
E = 4
B = 2
E = 5
B = 2
E = 0
3
3
3
8
1
b)
Dequeue
1
5
3
B = 1
E = 4
5
3
B = 2
E = 4
8
1
3
4
E = 2
B = 3
8
1
4
E = 2
B = 4
8
1
4
E = 2
B = 5
B = 0 E = 2
7
7
5
4
3
2
1
0
5
4
3
2
1
0
5
4
3
2
1
0
5
4
3
2
1
0
5
4
3
2
1
0
5
4
3
2
1
0
5
4
3
2
1
0
5
4
3
2
1
0
5
4
3
2
1
0
5
4
3
2
1
0
5
4
3
2
1
0
5
4
3
2
1
0
DSaA 2012/2013
Queue (an array)
typedef struct
{
int *arr;
int size;
int begin;
int end;
} Queue;
void init(Queue &queue, int size)
{
queue.begin=0;
queue.end=0;
queue.arr=new int[size+1];
queue.size=size+1;
}
bool empty(Queue queue)
{
return queue.begin==queue.end;
}
bool full(Queue queue)
{
return (queue.begin==0 && queue.end==queue.size-1)
|| (queue.begin==queue.end+1);
}
bool enqueue(Queue &queue, int elem)
{
if(full(queue))
return false;
queue.arr[queue.end++]=elem;
if(queue.end>=queue.size)
queue.end=0;
return true;
}
bool dequeue(Queue &queue, int &elem)
{
if(empty(queue))
return false;
elem=queue.arr[queue.begin++];
if(queue.begin>=queue.size)
queue.begin=0;
return true;
}
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
null
head
tail
Different
graphic
representation
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.
DSaA 2012/2013
Linked List (cont.)
head
head
head
5
5
2
7
20
empty list
one-element list
four-element list
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.
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.
typedef struct TagElemLL
{
int key;
TagElemLL *next;
} ElemLL;
typedef ElemLL *LinkedList;
void insertAsHead(LinkedList &head, int key)
{
ElemLL *newEl=new ElemLL;
newEl->key=key;
newEl->next=head;
head=newEl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
head
5
key
newEl
head
5
key
newEl
After {11}
?
head
5
key
After {12}
?
?
After {9}
newEl
?
5
head
5
key
After {13}
newEl
5
head
5
key
After {14}
newEl
5
DSaA 2012/2013
Linked List
– insertAsHead (cont.)
8
key
head
5
head
5
head
5
After {12}
After {13}
After {14}
8
?
newEl
8
newEl
8
newEl
head
4
head
4
head
4
After {12}
After {13}
After {14}
1
?
newEl
1
newEl
1
newEl
8
5
1
key
8
5
8
5
DSaA 2012/2013
Linked List
– findElem
ElemLL *findElem(
LinkedList head, int key)
{
ElemLL *p=head;
while(p!=null && p->key!=key)
p=p->next;
return p;
}
head
p
1
5
8
4
key
8
head
p
1
5
8
4
key
8
head
p
1
5
8
4
key
8
key
7
key
7
key
7
head
p
1
5
8
4
key
7
head
p
1
5
8
4
key
7
DSaA 2012/2013
Linked list
– removeHead
void removeHead(LinkedList &head)
{
if(head!=null)
{
ElemLL *p=head;
head=head->next;
delete p;
}
}
head
p
1
5
8
4
head
p
1
5
8
4
head
p
5
8
4
?
head
p
5
head
p
5
head
p
?
DSaA 2012/2013
Linked list - removeElem
head
x
1
5
8
4
....
....
p
7
Element to remove
head
x
1
5
8
4
....
....
p
7
1
5
4
....
....
7
x
p
?
1
5
4
....
....
7
head
head
Before removing
Changes
in predecessor
Removing
from memory
After removing
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.
5
2
7
20
head = begin of a queue
tail = end of a queue
DSaA 2012/2013
Linked list
– insertAsTail
typedef struct
{
ElemLL *head,*tail;
} LinkedList;
void insertAsTail(LinkedList &list, int key)
{
ElemLL *newEl=new ElemLL;
newEl->key=key;
newEl->next=null;
if(list.tail!=null)
list.tail->next=newEl;
else
list.head=newEl;
list.tail=newEl;
}
1
key
5
8
4
1
head
5
8
4
tail
newEl
1
head
5
8
4
tail
1
tail
head
newEl
newEl
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
one-element list
head
tail
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
3
head
tail
5
8
newEl
1
?
3
head
5
8
newEl
1
3
head
5
8
1
3
head
5
8
1
1)
2)
3)
4)
tail
tail
tail
newEl
newEl
as a head
DSaA 2012/2013
Double linked list
– insertElem …
in the middle
3
head
tail
5
8
1
3
head
1
newEl
?
p
tail
5
8
p
4
newEl
?
?
3
head
1
tail
5
8
p
4
newEl
3
head
1
tail
5
8
p
4
newEl
1)
2)
3)
4)
4
DSaA 2012/2013
Double linked list
– insertElem …
as a tail
1)
2)
3)
4)
3
head
tail
5
8
?
newEl
3
head
tail
5
8
newEl
9
?
3
head
tail
5
8
newEl
9
3
head
tail
5
8
newEl
9
DSaA 2012/2013
Double linked list
– insertElem …
typedef struct TagElemLL
{
int key;
TagElemLL *next,*prev;
} ElemLL;
typedef struct
{
ElemLL *head,*tail;
} DoubledLinkedList;
void insert(DoubledLinkedList list, int key)
{
ElemLL *newEl=new ElemLL;
newEl->key=key;
ElemLL *p=list.head;
while(p!=null && p->key<key)
p=p->next;
if(p==null)
{
newEl->next=null;
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
• List inner organisation:
– with head or tail
– with head and tail
• List end:
– ordinary-linked
– circularly-linked
• Specific lists:
– with sentinel
– cycled on last element
5
2
7
20
tail
DSaA 2012/2013
Advances, disadvances
• list vs arrar
– list:
• dynamic(+)
• unlimited(+)
• sequential access(-)
• extra storage(-),
– array:
• static(-)
• limited(-)
• random access(+)