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(+)