Data Structures and Agorithm: DS 05 Doubly Linked List.pptx

Data Structures and Agorithm: DS 05 Doubly Linked List.pptx

1. Data Structure Lecture No. 5 Doubly Linked List Engr . Rashid Farid Chishti http://youtube.com/rfchishti http://sites.google.com/site/chishti International Islamic University H-10, Islamabad, Pakistan Video Lecture

2. Moving forward in a singly-linked list is easy; moving backwards is not so easy . To move back one node, we have to start at the head of the singly-linked list and move forward until the node before the current. To avoid this we can use two pointers in a node: one to point to next node and another to point to the previous node : Need to be more careful when adding or removing a node. Consider add: the order in which pointers are reorganized is important: Doubly Linked List next prev d ata

3. current = current -> prev ; dnode *temp = new dnode ; temp -> data = num ; temp -> prev = current ; temp -> next = current -> next ; temp -> next -> prev = temp ; current -> next = temp ; Adding a new Node NULL temp head next prev 9 current next prev 6 NULL next prev 2 next prev 1

4. Deleting a Node next prev 2 NULL next prev 6 NULL next prev 2 next prev 9 void linklist :: d_delete ( int num ){ dnode *current = head ; while ( current != NULL ){ if ( current -> data == num ){ if ( current == head ){ head = head -> next ; head -> prev = NULL ; } else { if ( current -> next == NULL ) current -> prev -> next = NULL ; else { current -> prev -> next = current -> next ; current -> next -> prev = current -> prev ; } delete current ; } return ; } current = current -> next ; } cout << num << " not found." ; } head current num = 9 If it is the first node If it is the last node If it is any intermediate node

5. #include < iostream > using namespace std ; class linklist { private : struct dnode { dnode * prev ; int data ; dnode * next ; } *head ; public : linklist ( ) ; void d_append ( int num ) ; void d_addatbeg ( int num ) ; void d_addafter ( int loc , int num ) ; void d_display ( ) ; int d_count ( ) ; void d_delete ( int i ) ; ~ linklist ( ) ; } ; 5 Example 1 : Doubly Linked List linklist :: linklist ( ){ head = NULL ; } // adds a new node at the end void linklist :: d_append ( int num ){ dnode *r, *current ; current = head ; // if the linked list is empty if ( current == NULL ){ // create a new node current = new dnode ; current -> prev = NULL ; current -> data = num ; current -> next = NULL ; head = current ; } 1 2

6. else { // traverse the linked list while ( current -> next != NULL ) current = current -> next ; // add a new node at the end r = new dnode ; r -> data = num ; r -> next = NULL ; r -> prev = current ; current -> next = r ; } } // adds a new node at the begining void linklist :: d_addatbeg ( int num ){ dnode * newNode ; // create a new node newNode = new dnode ; 6 Example 1 : Doubly Linked List // assign data to the new node newNode -> prev = NULL ; newNode -> data = num ; newNode -> next = head ; // make new node the head node head -> prev = newNode ; head = newNode ; } // adds at a specified position void linklist :: d_addafter ( int loc, int num ) { dnode *current ; current = head ; // skip to desired portion for ( int i = 0 ; i < loc ; i++ ) { current = current -> next ; 3 4

7. // if reached at end of list if ( current == NULL ){ cout << "\ nThere are less than " << loc << " elements" ; return ; } } // insert new node current = current -> prev ; dnode *temp = new dnode ; temp -> data = num ; temp -> prev = current ; temp -> next = current -> next ; temp -> next -> prev = temp ; current -> next = temp ; } 7 Example 1 : Doubly Linked List // displays the the linked list void linklist :: d_display ( ){ dnode *temp = head ; cout << endl ; // traverse the entire linked list while ( temp != NULL ){ cout << temp -> data << " " ; temp = temp -> next ; } } // counts the number of nodes int linklist :: d_count ( ){ int c = 0 ; dnode *temp = head ; // traverse the entire linked list while ( temp != NULL ){ temp = temp -> next ; c ++ ; } 5 6

8. return c ; } // deletes the specified node void linklist :: d_delete ( int num ){ dnode *current = head ; // traverse the entire linked list while ( current != NULL ){ // if node to be deleted is found if ( current -> data == num ){ // if it is the first node if ( current == head ){ head = head -> next ; head -> prev = NULL ; } else { // if it is the last node if ( current -> next == NULL ) 8 Example 1 : Doubly Linked List current -> prev -> next = NULL ; else { // if it is any intermediate node current -> prev -> next = current -> next ; current -> next -> prev = current -> prev ; } delete current ; } // return back after deletion return ; } // go to next node current = current -> next ; } cout << "\n" << num << " not found." ; } 7 8

9. // deallocates memory linklist :: ~ linklist ( ){ while ( head != NULL ){ dnode *q = head; head = head -> next ; delete q ; } } int main( ){ linklist l ; l.d_append ( 11 ) ; l.d_append ( 2 ) ; l.d_append ( 14 ) ; l.d_append ( 17 ) ; l.d_append ( 99 ) ; cout << "\ nElements in doubly linked list: " ; 9 Example 1 : Doubly Linked List l.d_display ( ) ; cout << "\ nNo . of elements in the " doubly linked list: " << l.d_count (); l.d_addatbeg ( 33 ) ; l.d_addatbeg ( 55 ) ; cout << "\n\ nElements in doubly linked list after addition at the beginning: " ; l.d_display ( ) ; cout << "\ nNo . of elements in the doubly linked list: " << l.d_count ( ) ; l.d_addafter ( 4, 66 ) ; l.d_addafter ( 2, 96 ) ; cout << "\n\ nElements in doubly linked list after addition at the given position: " ; 9 10

10. l.d_display ( ) ; cout << "\ nNo . of elements in the doubly linked list: " << l.d_count ( ) ; l.d_delete ( 55 ) ; l.d_delete ( 2 ) ; l.d_delete ( 99 ) ; cout << "\n\ nElements in doubly linked list after deletion: " ; l.d_display ( ) ; cout << "\ nNo . of elements in the doubly linked list: \n" << l.d_count ( ) << endl ; system ( "PAUSE" ); return 0; } 10 Example 1 : Doubly Linked List 11 12

11. Doubly Linked List

12. Image viewer – Previous and next images are linked, hence can be accessed by next and previous button. Previous and next page in web browser – We can access previous and next url searched in web browser by pressing back and next button since, they are linked as linked list. Music Player – Songs in music player are linked to previous and next song. you can play songs either from starting or ending of the list . Applications of Doubly Linked List