Data structures & algorithms lecture 3

DATA STRUCTURES AND ALGORITHMS Lecture Notes 3 Prepared by İnanç TAHRALI

2 ROAD MAP  Abstract Data Types (ADT)  The List ADT  Implementation of Lists  Array implementation of lists  Linked list implementation of lists  Cursor implementation of lists

3 Abstract Data Types (ADT)  Definition : Is a set of operation Mathematical abstraction No implementation detail  Example : Lists, sets, graphs, stacks are examples of ADT along with their operations

4 Why ADT ?  Modularity  divide program into small functions  easy to debug and maintain  easy to modify  group work  Reuse  do some operations only once  Easy to change of implementation  transparent to the program

5 THE LIST ADT  Ordered sequence of data items called elements  A1, A2, A3, …,AN is a list of size N  size of an empty list is 0  Ai+1 succeeds Ai  Ai-1 preceeds Ai  position of Ai is i  first element is A1 called “head”  last element is AN called “tail” Operations ?

6 THE LIST ADT  Operations  PrintList  Find  FindKth  Insert  Delete  Next  Previous  MakeEmpty

7 THE LIST ADT  Example: the elements of a list are 34, 12, 52, 16, 12  Find (52)  3  Insert (20, 3)  34, 12, 52, 20, 16, 12  Delete (52)  34, 12, 20, 16, 12  FindKth (3)  20

8 Implementation of Lists  Many Implementations  Array  Linked List  Cursor (linked list using arrays)

10 Array Implementation of List ADT  Need to define a size for array  High overestimate (waste of space)  Operations Running Times PrintList O(N) Find Insert O(N) (on avarage half needs to be moved) Delete FindKth Next O(1) Previous

11 Array Implementation of List ADT  Disadvantages :  insertion and deletion is very slow  need to move elements of the list  redundant memory space  it is difficult to estimate the size of array

13 Linked List Implementation of Lists  Series of nodes  not adjacent in memory  contain the element and a pointer to a node containing its succesor  Avoids the linear cost of insertion and deletion !

14 Linked List Implementation of Lists  Insertion into a linked list

15 Linked List Implementation of Lists  Deletion from a linked list

16 Linked List Implementation of Lists  Need to know where the first node is  the rest of the nodes can be accessed  No need to move the list for insertion and deletion operations  No memory waste

17 Linked List Implementation of Lists Linked List Array PrintList O(N) (traverse the list) O(N) Find FindKth (L,i) O(i) O(1) Delete O(1) O(N)

18 Programming Details  There are 3 special cases for linked lists  Insert an element at the front of the list  there is no really obvious way  Delete an element from the front of the list  changes the start of the list  Delete an element in general  requires to keep track of the node before the deleted one How can we solve these three problems ?

19 Programming Details Keep a header node in position 0  Write a FindPrevious routine  returns the predecessor of the cell  To delete the first element  FindPrevious routine returns the position of header Use of header node is controversial !

20 Type decleration for link list node template <class Object> class List; // Incomplete declaration. template <class Object> class ListItr; // Incomplete declaration. template <class Object> class ListNode { ListNode( const Object & theElement = Object( ), ListNode*n=NULL) : element(theElement),next(n) {} Object element; ListNode *next; friend class List<Object>; friend class ListItr<Object>; };

21 Iterator class for linked lists template <class Object> class ListItr { public: ListItr( ) : current( NULL ) { } bool isPastEnd( ) const { return current == NULL; } void advance( ) { if( !isPastEnd( ) ) current = current->next; } const Object & retrieve( ) const { if( isPastEnd( ) ) throw BadIterator( ); return current->element; } private: ListNode<Object> *current; // Current position ListItr(ListNode<Object> *theNode):current( theNode ) { } friend class List<Object>; // Grant access to constructor };

22 List class interface template <class Object> class List { public: List( ); List( const List & rhs ); ~List( ); bool isEmpty( ) const; void makeEmpty( ); ListItr<Object> zeroth( ) const; ListItr<Object> first( ) const; void insert( const Object & x, const ListItr<Object> & p ); ListItr<Object> find( const Object & x ) const; ListItr<Object> findPrevious( const Object & x ) const; void remove( const Object & x ); const List & operator=( const List & rhs ); private: ListNode<Object> *header; };

23 Function to print a list template <class Object> void printList( const List<Object> &the List) { if (theList.isEmpty()) cout<< “Empty list” << endl; else { ListItr<Object> itr = theList.first(); for (; !itr.isPastEnd(); itr.advance()) cout << itr.retrieve() <<“ ”; } cout << endl; }

24 Some list one-liners /* Construct the list */ template <class Object> List<Object>::List( ) { header = new ListNode<Object>; } /* Test if the list is logically empty */ template <class Object> bool List<Object>::isEmpty( ) const { return header->next == NULL; }

25 Some list one liners /* Return an iterator representing the header node template <class Object> ListItr<Object> List<Object>::zeroth( ) const { return ListItr<Object>( header ); } /* Return an iterator representing the first node in the list. This operation is valid for empty lists. */ template <class Object> ListItr<Object> List<Object>::first( ) const { return ListItr<Object>( header->next ); }

26 Find routine /* Return iterator corresponding to the first node containing an item x. Iterator isPastEnd if item is not found. */ template <class Object> ListItr<Object> List<Object>::find( const Object & x ) const { ListNode<Object> *itr = header->next; while( itr != NULL && itr->element != x ) itr = itr->next; return ListItr<Object>( itr ); }

27 Deletion routine for linked lists /* Remove the first occurrence of an item x. */ template <class Object> void List<Object>::remove( const Object & x ) { ListItr<Object> p = findPrevious( x ); if( p.current->next != NULL ) { ListNode<Object> *oldNode = p.current->next; p.current->next = p.current->next->next; delete oldNode; } }

28 findPrevious-the find routine for use with remove /*Return iterator prior to the first node containing an item x. template <class Object> ListItr<Object> List<Object>::findPrevious( const Object & x ) const { ListNode<Object> *itr = header; while( itr->next != NULL && itr->next->element != x ) itr = itr->next; return ListItr<Object>( itr ); }

29 Insertion routine for linked lists /* Insert item x after p. */ template <class Object> void List<Object>::insert( const Object & x, const ListItr<Object> & p ) { if( p.current != NULL ) p.current->next = new ListNode<Object> ( x, p.current->next ); }

30 makeEmpty and List destructor /* Make the list logically empty. */ template <class Object> void List<Object>::makeEmpty( ) { while( !isEmpty( ) ) remove( first( ).retrieve( ) ); } /* Destructor */ template <class Object> List<Object>::~List( ) { makeEmpty( ); delete header; }

31 List copy routines: operator= /*Deep copy of linked lists. template <class Object> const List<Object> & List<Object>::operator=( const List<Object> & rhs ) { ListItr<Object> ritr = rhs.first( ); ListItr<Object> itr = zeroth( ); if( this != &rhs ) { makeEmpty( ); for( ; !ritr.isPastEnd( ); ritr.advance( ),itr.advance( )) insert( ritr.retrieve( ), itr ); } return *this; }

32 List copy routines : copy constructor /* Copy constructor template <class Object> List<Object>::List( const List<Object> & rhs ) { header = new ListNode<Object>; *this = rhs; }

33 Doubly Linked List  Traversing list backwards  not easy with regular lists  Insertion and deletion more pointer fixing  Deletion is easier  Previous node is easy to find

34 Circulary Linked List  Last node points the first

36 Cursor Implementation of Linked List Problems with linked list implementation:  Same language do not support pointers !  Then how can you use linked lists ?  new and free operations are slow  Actually not constant time

37 Cursor Implementation of Linked List SOLUTION: Implement linked list on an array called CURSOR

38 Cursor Implementation of Linked List  Cursor operation simulates the features  Collection of structures  uses array for nodes  Array index is pointer  new and delete operation  Keep a free list  new returns an element from freelist  delete place the node in freelist  Freelist  Use cell 0 as header  All nodes are free initially  0 is a NULL pointer

39 Cursor Implementation of Linked List If L = 5, then L represents list (A, B, E) If M = 3, then M represents list (C, D, F)

40 Iterator for cursor implementation of linked lists template <class Object> class ListItr { public: ListItr( ) : current( 0 ) { } bool isPastEnd( ) const {return current == 0; } void advance( ){ if( !isPastEnd( ) ) current = List<Object>::cursorSpace[ current ].next; } const Object & retrieve( ) const { if( isPastEnd( ) ) throw BadIterator( ); return List<Object>::cursorSpace[ current ].element; } private: int current; // Current position friend class List<Object>; ListItr( int theNode ) : current( theNode ) { } };

41 Class skeleton for cursor-based List template <class Object> class ListItr; // Incomplete declaration. template <class Object> class List { public: List( ); List( const List & rhs ); ~List( ); bool isEmpty( ) const; void makeEmpty( ); ListItr<Object> zeroth( ) const; ListItr<Object> first( ) const; void insert( const Object & x, const ListItr<Object> & p ); ListItr<Object> find( const Object & x ) const; ListItr<Object> findPrevious( const Object & x ) const; void remove( const Object & x );

42 Class skeleton for cursor-based List public: struct CursorNode { CursorNode( ) : next( 0 ) { } private: CursorNode( const Object & theElement, int n ) : element( theElement ), next( n ) {} Object element; int next; friend class List<Object>; friend class ListItr<Object>; }; const List & operator=( const List & rhs );

43 Class skeleton for cursor-based List private: int header; static vector<CursorNode> cursorSpace; static void initializeCursorSpace( ); static int alloc( ); static void free( int p ); friend class ListItr<Object>; };

44 cursorSpace initialization /* Routine to initialize the cursorSpace. */ template <class Object> void List<Object>::initializeCursorSpace( ) { static int cursorSpaceIsInitialized = false; if( !cursorSpaceIsInitialized ) { cursorSpace.resize( 100 ); for( int i = 0; i < cursorSpace.size( ); i++ ) cursorSpace[ i ].next = i + 1; cursorSpace[ cursorSpace.size( ) - 1 ].next = 0; cursorSpaceIsInitialized = true; } }

45 Routines : alloc and free /* Allocate a CursorNode template <class Object> int List<Object>::alloc( ) { int p = cursorSpace[ 0 ].next; cursorSpace[ 0 ].next = cursorSpace[ p ].next; return p; } /* Free a CursorNode template <class Object> void List<Object>::free( int p ) { cursorSpace[ p ].next = cursorSpace[ 0 ].next; cursorSpace[ 0 ].next = p; }

46 Short routines for cursor-based lists /* Construct the list template <class Object> List<Object>::List( ) { initializeCursorSpace( ); header = alloc( ); cursorSpace[ header ].next = 0; } /* Destroy the list template <class Object> List<Object>::~List( ) { makeEmpty( ); free( header ); }

47 Short routines for cursor-based lists /* Test if the list is logically empty. return true if empty template <class Object> bool List<Object>::isEmpty( ) const { return cursorSpace[ header ].next == 0; } /* Return an iterator representing the first node in the list. This operation is valid for empty lists. template <class Object> ListItr<Object> List<Object>::first( ) const { return ListItr<Object>( cursorSpace[ header ].next ); }

48 find routine - cursor implementation /*Return iterator corresponding to the first node containing an item x. Iterator isPastEnd if item is not found. template <class Object> ListItr<Object> List<Object>::find( const Object & x ) const { int itr = cursorSpace[ header ].next; while( itr != 0 && cursorSpace[ itr ].element != x ) itr = cursorSpace[ itr ].next; return ListItr<Object>( itr ); }

49 insertion routine-cursor implementation /* Insert item x after p. template <class Object> void List<Object>::insert(const Object & x,const ListItr<Object> & p) { if( p.current != 0 ) { int pos = p.current; int tmp = alloc( ); cursorSpace[ tmp ] = CursorNode( x, cursorSpace[ pos ].next ); cursorSpace[ pos ].next = tmp; } }

50 deletion routine - cursor implementation /* Remove the first occurrence of an item x. template <class Object> void List<Object>::remove( const Object & x ) { ListItr<Object> p = findPrevious( x ); int pos = p.current; if( cursorSpace[ pos ].next != 0 ) { int tmp = cursorSpace[ pos ].next; cursorSpace[ pos ].next = cursorSpace[ tmp ].next; free ( tmp ); } }

Data structures & algorithms lecture 3

In this document

More Related Content

What's hot

Viewers also liked

Similar to Data structures & algorithms lecture 3

More from Poojith Chowdhary

Recently uploaded

Data structures & algorithms lecture 3