Data Structures
Lists
Hikmat Farhat
March 7, 2013
Hikmat Farhat
Data Structures
March 7, 2013
1 / 39
Introduction
A list is a sequentially organized set of elements.
Generalization of arrays.
many kinds of lists:
I
I
I
singly linked lists.
doubly linked lists.
circular lists.
Hikmat Farhat
Data Structures
March 7, 2013
1 / 39
Operations on lists
a list object should implement the following operations
I
I
I
I
I
I
I
create: create the list.
push back: add an item to the end of the list.
insert: insert an item in the list at an arbitrary position.
pop back: delete an item from the end of the list
erase: delete an item from a certain position or a range.
empty: test wether the list is empty or not.
find: search for the existance of an element in the list.
Hikmat Farhat
Data Structures
March 7, 2013
2 / 39
Vector Implementation
One data structure provide by the Standard Template Library (stl) is
the vector class.
First we will use the stl vector class and see how it implements the list
ADT.
A vector implementation is a suitable implementation when
I
I
Elements are added/deleted only from the end of the list
Finding element at position k is used often and must be fast.
It is fast in access elements at random positions
More importantly: a vector implementation is not suitable when we
need to add/remove the front element.
Hikmat Farhat
Data Structures
March 7, 2013
3 / 39
Iterators
There are many times where we need to iterate through the
elements of a list.
We do this regardless how the list is implemented.
A convenient way of doing this is to use iterators
An iterator is simply a pointer to an element of the list
An iterator supports increments methods.
Hikmat Farhat
Data Structures
March 7, 2013
4 / 39
Using Iterators to print all elements of vector
#i n c l u d e <i o s t r e a m >
#i n c l u d e <v e c t o r >
#i n c l u d e <s t r i n g >
u s i n g namespace s t d ;
i n t p r i n t ( v e c t o r <s t r i n g > & v ) {
/ add
v . push
v . push
v . push
s t r i n g e l e m e n t s /
back ( f i r s t s t r i n g ) ;
back ( second s t r i n g ) ;
back ( t h i r d s t r i n g ) ;
v e c t o r <s t r i n g > : : i t e r a t o r
itr ;
f o r ( i t r =v . b e g i n ( ) ; i t r != v . end ( ) ; i t r ++)
cout << i t r <<e n d l ;
return 0;
}
Hikmat Farhat
Data Structures
March 7, 2013
5 / 39
Using Iterators to insert and remove elements
v e c t o r <s t r i n g > : : i t e r a t o r i t r ;
/ i n s e r t an e l e m e n t between
f i r s t and s e c o n d e l e m e n t s /
i t r =v . b e g i n ( ) ;
i t r ++;
v . i n s e r t ( i t r , between 1 & 2 ) ;
/ e r a s e t h e e l e m e n t b e f o r e t h e l a s t /
/ t h e l a s t e l e m e n t i s a t v . end () 1 /
i t r =v . end ( ) ;
i t r =2;
v . erase ( i t r );
f o r ( i t r =v . b e g i n ( ) ; i t r != v . end ( ) ; i t r ++)
cout << i t r <<e n d l ;
return 0;
Listing 2: insertion and deletion
Hikmat Farhat
Data Structures
March 7, 2013
6 / 39
STL list class
A different implementation of the list ADT is the STL list
Unlike the vector class which uses an array for internal storage
the list is implemented as a linked list.
Unlike vector it provides an efficient implementation of push front
and pop front methods.
Unlike vector it does NOT provide an efficient implementation of
element at position k.
Hikmat Farhat
Data Structures
March 7, 2013
7 / 39
Using STL list
#i n c l u d e <i o s t r e a m >
#i n c l u d e < l i s t >
u s i n g namespace s t d ;
i n t main ( i n t a r g c , c o n s t c h a r a r g v [ ] ) {
l i s t <s t r i n g > m y l i s t ;
m y l i s t . p u s h f r o n t ( f i r s t element ) ;
m y l i s t . push back ( second element ) ;
m y l i s t . p u s h f r o n t ( t h i r d element ) ;
l i s t <s t r i n g > : : i t e r a t o r
itr ;
f o r ( i t r =m y l i s t . b e g i n ( ) ; i t r != m y l i s t . end ( ) ; i t r ++)
cout << i t r <<e n d l ;
return 0;
}
Hikmat Farhat
Data Structures
March 7, 2013
8 / 39
Vector interface
#i f n d e f l i s t v e c t o r V e c t o r h
#d e f i n e l i s t v e c t o r V e c t o r h
t e m p l a t e <typename O b j e c t>
c l a s s Vector
{
private :
int theSize ;
int theCapacity ;
Object o b j e c t s ;
public :
e x p l i c i t V e c t o r ( i n t i n i t S i z e =0);
Vector ( const Vector & rhs ) ;
Vector ( ) ;
c o n s t V e c t o r & o p e r a t o r= ( c o n s t V e c t o r & r h s ) ;
void r e s i z e ( i n t newCapacity ) ;
Object & operator [ ] ( i n t index ) ;
b o o l empty ( ) c o n s t ;
i n t s i z e ( ) c o n s t ; / / how many e l e m e n t s ?
i n t capacity ( ) const ;// t o t a l capacity
void push back ( const Object & x ) ;
void pop back ( ) ;
typedef Object i t e r a t o r ;
i t e r a t o r begin ( ) ;
i t e r a t o r end ( ) ;
};
Hikmat Farhat
Data Structures
March 7, 2013
9 / 39
Adding an element to Vector
t e m p l a t e <typename O b j e c t>
v o i d V e c t o r<O b j e c t >:: p u s h b a c k ( c o n s t O b j e c t & x )
{
i f ( t h e S i z e == t h e C a p a c i t y )
r e s i z e ( 2 theCapacity );
o b j e c t s [ t h e S i z e++ ] = x ;
}
In the code above sometimes we need to call the expensive resize .
t e m p l a t e <typename O b j e c t>
v o i d V e c t o r<O b j e c t >:: r e s i z e ( i n t n e w C a p a c i t y )
{
i f ( newCapacity < t h e S i z e )
return ;
Object oldArray = o b j e c t s ;
o b j e c t s = new O b j e c t [ n e w C a p a c i t y ] ;
f o r ( i n t k = 0 ; k < t h e S i z e ; k++ )
objects [ k ] = oldArray [ k ] ;
theCapacity = newCapacity ;
delete [ ] oldArray ;
}
Hikmat Farhat
Data Structures
March 7, 2013
10 / 39
Vector Implementation
t e m p l a t e <typename O b j e c t>
V e c t o r<O b j e c t >:: V e c t o r ( i n t i n i t S i z e )
: theSize ( i n i t S i z e ) , theCapacity ( i n i t S i z e )
{ o b j e c t s=new O b j e c t [ t h e C a p a c i t y ] ; }
t e m p l a t e <typename O b j e c t>
V e c t o r<O b j e c t >:: V e c t o r ( c o n s t V e c t o r<O b j e c t>& r h s ) : t h e S i z e ( r h s . s i z e ( ) ) ,
theCapacity ( rhs . theCapacity )
{
o b j e c t s = new O b j e c t [ c a p a c i t y ( ) ] ;
f o r ( i n t k = 0 ; k < s i z e ( ) ; k++ )
objects [ k ] = rhs . objects [ k ] ;
}
t e m p l a t e <typename O b j e c t>
V e c t o r<O b j e c t >:: V e c t o r ( )
{ d e l e t e [ ] o b j e c t s ;}
t e m p l a t e <typename O b j e c t>
c o n s t V e c t o r<O b j e c t> & V e c t o r<O b j e c t >:: o p e r a t o r= ( c o n s t V e c t o r<O b j e c t>& r h s )
i f ( t h i s != &r h s )
{
delete [ ] objects ;
t h e S i z e=r h s . s i z e ( ) ;
t h e C a p a c i t y=r h s . c a p a c i t y ( ) ;
o b j e c t s=new O b j e c t [ c a p a c i t y ( ) ] ;
f o r ( i n t k =0; k<s i z e ( ) ; k++)
o b j e c t s [ k ]= r h s . o b j e c t s [ k ] ;
}
return this ;
}
Hikmat Farhat
Data Structures
March 7, 2013
11 / 39
Vector Implementation
t e m p l a t e <typename O b j e c t>
v o i d V e c t o r<O b j e c t >:: r e s i z e ( i n t n e w C a p a c i t y )
{
i f ( newCapacity < t h e S i z e )
return ;
Object oldArray = o b j e c t s ;
o b j e c t s = new O b j e c t [ n e w C a p a c i t y ] ;
f o r ( i n t k = 0 ; k < t h e S i z e ; k++ )
objects [ k ] = oldArray [ k ] ;
theCapacity = newCapacity ;
delete [ ] oldArray ;
}
t e m p l a t e <typename O b j e c t>
O b j e c t & V e c t o r<O b j e c t >:: o p e r a t o r [ ] (
{ return objects [ index ] ; }
int index )
t e m p l a t e <typename O b j e c t>
b o o l V e c t o r<O b j e c t >:: empty ( ) c o n s t
{ r e t u r n s i z e ( ) == 0 ; }
Hikmat Farhat
Data Structures
March 7, 2013
12 / 39
inserting elements in the vector is a costly operation because a whole
portion of the array needs to be copied.
the worst case happens when the insertion is done on the front.
This is why the vector class supports inserts at the end only.
Even in that case it becomes costly when we run out of space and we
need to increase the storage
check the method resize(int ) in our implementation of vector.
Hikmat Farhat
Data Structures
March 7, 2013
13 / 39
Why a copy constructor?
A copy constructor is used by the compiler in the following cases
I
When an argument is passed by value, a copy of the argument should
be made
when a function returns a local object (not a pointer or reference to it),
an anonymous and temporary copy should be made to be returned to
the caller.
when a object is initialized as: Type obj(initial obj) then obj is made as
a copy of initial obj using the copy constructor.
the compiler usually supplies a default copy constructor.
when there is dynamic memory allocation this default copy
constructor does not work.
Hikmat Farhat
Data Structures
March 7, 2013
14 / 39
why a destructor?
When an object goes out of scope it is destroyed.
This is done by calling the destrcutor method.
if no destrcutor method is specified the compiler uses a default one.
If memory was allocating dynamically through a pointer, the default
destructor destroys the pointer and NOT the memory that the pointer
points to.
therefore when memory is allocated dynamically it should be
destroyed manually through the destructor.
Hikmat Farhat
Data Structures
March 7, 2013
15 / 39
Linked lists
We need to be able to change the size of the list dynamically. this is
not possible with an array implementation.
the implementation of insert and delete is very inefficient.
An implementation that satisfies the above two condition is a linked
list structure:
I
I
Elements do not need to be store consecutively.
But then we need to link the elements together.
Hikmat Farhat
Data Structures
March 7, 2013
16 / 39
A linked list is a sequence of nodes
Each node has two parts:
I
I
I
I
I
Data part: information stored in that particular node.
Next part: a link (pointer) to the next node.
We only need to have a pointer to the first node.
the next part of the last node is null.
In this case we use a doubly linked list where each node has a next and
prev pointers.
Hikmat Farhat
Data Structures
March 7, 2013
17 / 39
Sentinel Node
For convenience, we use empty nodes, called sentinel, for head and
tail.
The first element in the list is the node just after the head.
The last element in the list is the node just before the tail.
Hikmat Farhat
Data Structures
March 7, 2013
18 / 39
Operations on Linked Lists
We would liked to have the following operations implemented on linked
lists.
create a list.
test if the list is empty.
display the list.
search for an item in the list.
delete an item from the list.
insert an item into the list.
Hikmat Farhat
Data Structures
March 7, 2013
19 / 39
Most operations will make use of an iterator
In this case an iterator will be a node with extra operations
Like itr++, itr, itr=, itr!=, *itr
All elements of the list are also accessed through iterators
{
Object data ;
Node p r e v ;
Node n e x t ;
Node ( c o n s t O b j e c t & d=O b j e c t ( ) , Node p=NULL ,
Node n=NULL)
: data ( d ) , prev ( p ) , next ( n ){}
};
Hikmat Farhat
Data Structures
March 7, 2013
20 / 39
Iterator Class
class iterator{
protected :
Node c u r r e n t ;
public :
i t e r a t o r (){}
i t e r a t o r ( Node p ) : c u r r e n t ( p){}
Object & o p e r a t o r ()
{ r e t u r n c u r r e n t >d a t a ; }
i t e r a t o r & o p e r a t o r ++(){
c u r r e n t=c u r r e n t >n e x t ;
return this ;
}
i t e r a t o r & o p e r a t o r ++( i n t i n ){
c u r r e n t=c u r r e n t >n e x t ;
return this ;
}
i t e r a t o r & o p e r a t o r (){
c u r r e n t=c u r r e n t >p r e v ;
return this ;
}
i t e r a t o r & o p e r a t o r (i n t i n ){
c u r r e n t=c u r r e n t >p r e v ;
return this ;
}
b o o l o p e r a t o r ==( c o n s t
i t e r a t o r & rhs ) const
{ r e t u r n c u r r e n t==r h s . c u r r e n t ; }
b o o l o p e r a t o r !=( c o n s t i t e r a t o r &r h s ) c o n s t
{ r e t u r n ! ( c u r r e n t==r h s . c u r r e n t ) ; }
f r i e n d c l a s s L i s t <O b j e c t >;
};
Hikmat Farhat
Data Structures
March 7, 2013
21 / 39
Empty list
Since we always have sentinel nodes an empty list has two nodes:
head and tail
Hikmat Farhat
Data Structures
March 7, 2013
22 / 39
beginning and end
The beginning and end are usually used differently
for example
f o r ( i t r = l i s t . b e g i n ( ) ; i t r != l i s t . end ( ) ; i t r ++)
In the code above, begin() should return the first element (i.e the one
after head)
Whereas end should return tail thus
iterator
return
}
iterator
return
}
Hikmat Farhat
begin (){
i t e r a t o r ( head>n e x t ) ;
end ( ) {
iterator ( tail );
Data Structures
March 7, 2013
23 / 39
Inserting a Node
i t e r a t o r i n s e r t ( i t e r a t o r i t r , const Object & x )
{
Node p= i t r . c u r r e n t ;
t h e S i z e ++;
Node newNode=new Node ( x , p>p r e v , p ) ;
p>p r e v >n e x t=newNode ;
p>p r e v=newNode ;
r e t u r n i t e r a t o r ( newNode ) ;
}
Hikmat Farhat
Data Structures
March 7, 2013
24 / 39
Deleting a node
i t e r a t o r e r a s e ( i t e r a t o r i t r ){
Node p= i t r . c u r r e n t ;
i t e r a t o r r e t ( p>n e x t ) ;
p>p r e v >n e x t=p>n e x t ;
p>n e x t >p r e v=p>p r e v ;
delete p;
t h e S i z e ;
return ret ;
}
Hikmat Farhat
Data Structures
March 7, 2013
25 / 39
List Destructor
Every time we add a node to the list we allocate additional memory.
When the list is out of scope and need to be destroyed, dynamically
allocated memory is not destroyed automatically.
Therefore we need to provide an explicit destructor for the
dynamically allocated memory.
Similarly we need to provide a copy constructor and define an
assignment operator.
Hikmat Farhat
Data Structures
March 7, 2013
26 / 39
clear ();
d e l e t e head ;
delete t a i l ;
}
L i s t & o p e r a t o r =( L i s t &r h s )
{
pop front ();
}
Object & f r o n t ( )
void pop back ( )
{ e r a s e ( end ( ) ) ; }
Hikmat Farhat
Data Structures
March 7, 2013
27 / 39
Difference between vector and list
Vector
I
I
Insertion and deletion are (n)
Direct access is (1)
Linked list
I
I
Insertion and deletion are (1)
Direct access is (n)
Hikmat Farhat
Data Structures
March 7, 2013
28 / 39
Stack ADT
A stack is a list of elements where only the top element is accessible
Operations are
I
I
push to put a new element at the top
pop to remove the top element
Hikmat Farhat
Data Structures
March 7, 2013
29 / 39
Stack implementation
We can use linked list but since insertion and deletion is done only at
the top it is better to use an array
Since only the top of the stack is accessible, insertion and deletion is
done efficiently
We need the following operations top(),push(),pop()
The stack has :
I
I
I
capacity
top of stack
array of objects
Hikmat Farhat
Data Structures
March 7, 2013
30 / 39
Stack Implementation
t e m p l a t e <typename O b j e c t >
c l a s s Stack
{
private :
i n t topOfStack ;
int theCapacity ;
Object o b j e c t s ;
void r e s e r v e ( i n t newCapacity ) ;
public :
S t a c k ( i n t c a p a c i t y =0)
: theCapacity ( capacity ? capacity :16)
{ t o p O f S t a c k =1;
o b j e c t s=new O b j e c t [ t h e C a p a c i t y ] ;
}
Stack ( const Stack & rhs )
{ o p e r a t o r =( r h s ) ; }
Stack ( )
{ delete [ ] objects ;}
Hikmat Farhat
Data Structures
March 7, 2013
31 / 39
Stack Implementation
c o n s t S t a c k & o p e r a t o r= ( c o n s t S t a c k & r h s ) ;
int s i z e ( ) const {
r e t u r n t o p O f S t a c k +1;
}
v o i d push ( c o n s t O b j e c t & x ) {
i f ( t o p O f S t a c k== t h e C a p a c i t y 1 )
reserve ( 2 theCapacity + 1 );
o b j e c t s [++ t o p O f S t a c k ]= x ;
}
v o i d pop ( ) {
// c h e c k f o r e r r o r
t o p O f S t a c k ;
}
Object top (){
r e t u r n o b j e c t s [ topOfStack ] ;
}
};
Hikmat Farhat
Data Structures
March 7, 2013
32 / 39
Assignment Operator
t e m p l a t e <typename O b j e c t >
c o n s t Stack <O b j e c t > & Stack <O b j e c t > : : o p e r a t o r= ( c o n s t Stack
{
i f ( t h i s != &r h s )
{
delete [ ] objects ;
t o p O f S t a c k = r h s . s i z e ( ) 1;
theCapacity = rhs . theCapacity ;
o b j e c t s = new O b j e c t [ t h e C a p a c i t y ] ;
f o r ( i n t k = 0 ; k < s i z e ( ) ; k++ )
objects [ k ] = rhs . objects [ k ] ;
}
return this ;
}
Hikmat Farhat
Data Structures
March 7, 2013
33 / 39
Overflow
t e m p l a t e <typename O b j e c t >
v o i d Stack <O b j e c t > : : r e s e r v e ( i n t n e w C a p a c i t y )
{
i f ( n e w C a p a c i t y < t o p O f S t a c k+1 )
return ;
Object oldArray = o b j e c t s ;
o b j e c t s = new O b j e c t [ n e w C a p a c i t y ] ;
f o r ( i n t k = 0 ; k < t o p O f S t a c k +1; k++ )
objects [ k ] = oldArray [ k ] ;
theCapacity = newCapacity ;
delete [ ] oldArray ;
}
Hikmat Farhat
Data Structures
March 7, 2013
34 / 39
Stack Application: Postfix Calculator
regular expressions are called infix expressions:
17 + 3 5
is interpreted as:
17 + (3 5)
because has higher precedence than +.
Postfix expressions are easier to evaluate because we dont need to
remember precedence rules. The above in postfix notation is
3 5 17+
Hikmat Farhat
Data Structures
March 7, 2013
35 / 39
A postfix calculator can be implemented using a stack as follows
1
2
If a number is read then it is pushed on the stack.
when an operator is read then
1
2
3
the appropriate number of arguments (usually two) are poped from the
stack.
the operator is applied to the arguments
The results is pushed back onto the stack.
Example, evaluate 6 5 2 3 + 8 * + 3 + *
Hikmat Farhat
Data Structures
March 7, 2013
36 / 39
Queue ADT
The basic operations on a Queue are
1
2
Enqueue to add an element to the end of a list
Dequeue to return ( and remove) the front element of a list
This why sometimes it is called First in First Out (FIFO).
Hikmat Farhat
Data Structures
March 7, 2013
37 / 39
Array Implementation of Queue ADT
A queue can be implemented using an array by maintaining two
values
I
I
front that points to the first element
back that points to end of the queue (last+1).
Hikmat Farhat
Data Structures
March 7, 2013
38 / 39
front
Initially
After enqueue(7)
12
back
12
After dequeue()
Hikmat Farhat
back
front
back
After enqueue(12)
front
5
back
Data Structures
front
March 7, 2013
39 / 39
