Data Structures and Agorithm: DS 04 Linked List.pptx

Data Structures and Agorithm: DS 04 Linked List.pptx

1. Data Structure Lecture No. 4 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. Linked List head 2 6 8 7 current 1 NULL 0x100 6 0x108 2 0x10C 0x110 0x114 7 0x118 0x11C 8 0x120 1 0x124 0x128 0x000 0x12C 0x11C 0x130 head current 2 6 8 7 1 0x10C 0x100 0x11C 0x114 0x100

3. push_front ( int Data){ node * newNode ; // add new node newNode = new node ; newNode -> data = Data ; newNode -> next = head ; head = newNode ; } Linked List Operations head 2 6 1 NULL head NULL NULL 9 newNode newNode 9 Data = 9

4. void push_back ( int Data ){ node * current, * newNode ; // list is empty then create first node if ( head == NULL ){ head = new node ; head -> data = Data ; head -> next = NULL ; } else { // go to last node current = head ; while ( current -> next != NULL ) current = current -> next ; newNode = new node ; newNode -> data = Data ; newNode -> next = NULL ; current -> next = newNode ; } } Linked List Operations head current 2 6 1 NULL head newNode NULL NULL 9 9 NULL Data = 9

5. void addafter ( int loc , int Data){ node * current = head, * newNode ; // skip to desired portion for ( int i = 0 ; i < loc ; i++ ) { current = current -> next ; // if reached at end of linked list if ( current == NULL ){ cout << "\ nThere are less than " << loc << " elements in list" << endl ; return ; } } newNode = new node ; // insert new node newNode -> data = Data ; newNode -> next = current -> next ; current -> next = newNode ; } Linked List Operations current 2 6 1 NULL head 9 newNode i = 1 loc = 1 Data = 9

6. void del ( int Data ) { node *previous, *current ; current = head ; while ( current != NULL ){ if ( current -> data == Data ){ if ( current == head ) head = current -> next ; else previous->next = current->next; delete current ; return ; } else { previous = current ; current = current -> next ; } } cout << "\n\ nElement " << Data << " not found" ; } Linked List Operations head NULL 1 current previous Data = 1

7. void del ( int Data ) { node *previous, *current ; current = head ; while ( current != NULL ){ if ( current -> data == Data ){ if ( current == head ) head = current -> next ; else previous->next = current->next; delete current ; return ; } else { previous = current ; current = current -> next ; } } cout << "\n\ nElement " << Data << " not found" ; } Linked List Operations current 2 6 head 9 NULL 1 previous previous Data = 1

8. # include < iostream > using namespace std ; class Linked_List { private : struct node{ int data ; node * next ; } * head ; public : Linked_List ( ) ; void push_back ( int Data ) ; void push_front ( int Data ) ; void addafter ( int loc , int Data ) ; void display ( ) ; int count ( ) ; void del ( int num ) ; ~ Linked_List ( ) ; } ; 8 Example 1 : Linked List Linked_List :: Linked_List ( ){ head = NULL ; } // adds node at the end of linked list void Linked_List :: push_back ( int Data ){ node *current, * newNode ; // list is empty then create first node if ( head == NULL ){ head = new node ; head -> data = Data ; head -> next = NULL ; } else { // go to last node current = head ; while ( current -> next != NULL ) current = current -> next ; // add node at the end 1 2

9. newNode = new node ; newNode -> data = Data ; newNode -> next = NULL ; current -> next = newNode ; } } // adds a node at the beginning void Linked_List :: push_front ( int Data){ node * newNode ; // add new node newNode = new node ; newNode -> data = Data ; newNode -> next = head ; head = newNode ; } // adds node after numbers of nodes void Linked_List :: addafter ( int loc , int num ){ 9 Example 1 : Linked List node *current, * newNode ; current = head ; // skip to desired portion for ( int i = 0 ; i < loc ; i++ ) { current = current -> next ; // if reached at end of linked list if ( current == NULL ){ cout << "\ nThere are less than " << loc << " elements in list" << endl ; return ; } } newNode = new node ; // insert new node newNode -> data = num ; newNode -> next = current -> next ; current -> next = newNode ; } 3 4

10. // displays the contents of the link list void Linked_List :: display( ){ node *current = head ; cout << endl ; // traverse the entire linked list while ( current != NULL ){ cout << current -> data << " " ; current = current -> next ; } } // counts the number of nodes present int Linked_List :: count( ){ node *current = head ; int c = 0 ; // traverse the entire linked list while ( current != NULL ){ current = current -> next ; c ++ ; } return c ; } 10 Example 1 : Linked List // deletes the specified node void Linked_List :: del ( int Data ) { node *previous, *current ; current = head ; while ( current != NULL ){ if ( current -> data == Data ){ // if node to be deleted is the // first node in the linked list if ( current == head ) head = current -> next ; else previous->next = current->next; // free memory occupied by node delete current ; return ; } // traverse the linked list till // the last node is reached 5 6

11. else { previous = current ; // go to the next node current = current -> next ; } } cout << "\n\ nElement " << Data << " not found" ; } // deallocates memory Linked_List :: ~ Linked_List ( ){ while ( head != NULL ){ node *current = head; head = head -> next ; delete current ; } } 11 Example 1 : Linked List int main( ) { Linked_List l ; l.push_back (14) ; l.push_back (30) ; l.push_back (25) ; l.push_back (42) ; l.push_back (17) ; cout << "\ nData in the linked list: " ; l.display ( ) ; l.push_front (999) ; l.push_front (888) ; l.push_front (777) ; cout << "\ n\ nData in the linked list " " after addition at the " " beginning: " ; l.display ( ) ; l.addafter (7, 0); l.addafter (2,1); l.addafter (5,99); cout << "\ n\ nData in the linked list" " after addition at given" " position: " ; 7 8

12. l.display ( ) ; cout << "\ nNo . of elements in the " " linked list " << l.count ( ); l.del (99) ; l.del ( 1) ; l.del (10) ; cout << "\ n\ nData in the linked list" " after deletion: " ; l.display ( ) ; cout << "\ nNo . of elements in the" " linked list: " << l.count (); system("PAUSE"); return 0; } 12 Example 1 : Linked List 9 10

13. Example 1: Linked List

14. push_front () we simply insert the new node after the current node. So add is a one-step operation. push_back () we have to traverse the entire list to insert the new node at the end of Linked List. del() We first search the node to be deleted. worst-case: may have to search the entire list Moving forward in a singly-linked list is easy but moving backwards is not so easy. Moving backwards requires traversing the list from the start until the node whose next pointer points to current node. Analysis of Linked List

15. Dynamic memory allocation : We use linked list of free blocks. Implementation of stacks and queues Maintaining directory of names. Performing arithmetic operations on long integers Addition and Multiplication of Polynomials. Implementation of Graphs . (Adjacency list representation of Graph ). Representing sparse matrices. For separate chaining in Hashtables . Undo functionality in Photoshop or Word . Linked list of states. Graph Plotting Application. Applications of Linked List

16. In single linked list, every node points to its next node in the sequence and the last node points to NULL . But in circular linked list, every node points to its next node in the sequence but the last node points to the first node in the list . Circular Linked List

17. The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed. Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player's chance ends. Circular Linked List can also be used to create Circular Queue . In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one pointer is required. Applications of Circular Linked List