Linked list and its operations - Traversal

Linked List and its operations

1. LINKED LIST Mrs. K. Kasthuri ., M.Sc., M.Phil., M.Tech ., Assistant Professor of IT, V.V.Vanniaperumal College for Women, Virudhunagar .

2. L INKED LIST DEFINITI0N A linked list is a data structure that stores a sequence of elements. Each element in the list is called a node, and each node has a reference to the next node in the list. The first node in the list is called the head, and the last node in the list is called the tail.

3. Linked List uses These nodes hold both the data and a reference to the next node in the list. Linked lists are often used because of their efficient insertion and deletion. They can be used to implement stacks, queues, and other abstract data types.

4. TYPE OF LInKED LIst

5. SINGLE LINKEDLIST A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail). Each element in a linked list is called a node. A single node contains data and a pointer to the next node which helps in maintaining the structure of the list. class Node { public: int data; Node* next; }

6. T he singly linked list is used to implement stack and queue. The undo or redo options, the back buttons, etc., that we discussed above are implemented using a singly linked list. During the implementation of a hash function, there arises a problem of collision, to deal with this problem, a singly linked list is used. USES

7. SINGLE LINKEDLIST Traversing the list Inserting a node into the first Deleting a node from the list Merging the linked list Copying the list Searching the list

8. Operations on Singly Linked List:: The following operations are performed on a Single LinkedList Traversing: Displaying the contents of a linked list is very simple. Insertion:   The insertion operation can be performed in three ways. They are as follows... Inserting At the Beginning of the list Inserting At End of the list Inserting At Specific location in the list Deletion:   The deletion operation can be performed in three ways. They are as follows… Deleting from the Beginning of the list Deleting from the End of the list Deleting a Specific Node Search:  It is a process of determining and retrieving a specific node either from the front, the end or anywhere in the list. Merging: The merge point is where both lists point to the same node, i.e. they reference the same memory location

9. Traverse a Linked List Displaying the contents of a linked list is very simple. We keep moving the temp node to the next one and display its contents.When  temp is NULL, we know that we have reached the end of the linked list so we get out of the while loop. void list:: traverse _list (){ node*new1,node*head ; new1= new Node; new1->data = item ; new1->next = NULL;}

10. 1. Insert at the Beginning Allocate memory for new node Store data Change next of new node to point to head Change head to point to recently created node 2. Insert at the End Allocate memory for new node Store data Traverse to last node Change next of last node to recently created node void list:: insert_end (){ n ode *new1, n ode *head ;{ new1= new node;new1->data = item ;new1->next= NULL; while ( ptr -> next != null){ ptr = ptr -> next; } Ptr -> next = new1;} void list:: inserte_begining (){ node*new1,node*head; new1= new Node; new1->data = item ; new1->next = NULL;}

11. 3.Insert at the Middle Allocate memory and store data for new node Traverse to node just before the required position of new node Change next pointers to include new node in between Void list:: insert_end (){ n ode *new1,node*head, int position { new1->data =item; ptr =head; while ( ptr -> data!=position){ ptr = ptr ->next; } new1->next = ptr -> next; ptr -> next = new1; } DELETE FROM SINGLE LINKEDLIST

12. 2. Delete from End Traverse to second last element Change its next pointer to null void list:: delete_begining (){ n ode*head; { item=head->data; head = head->next;}} 1. Delete from Beginning Point head to the second node void list:: deleteLast (){ Node*head,* ptr ,* prev ; { ptr = head; while ( ptr ->next->next != null){ prev = ptr ; ptr = ptr -> next; } prev -> next = NULL; }

13. 3. Delete from Middle Traverse to element before the element to be deleted Change next pointers to exclude the node from the chain void list:: delete_middle () n ode*head,* ptr ; int position { ptr = head; while ( ptr -> data != popsition ){ ptr = ptr -> next; } ptr -> next= ptr -> next->next; }

14. Search an Element on a Linked List You can search an element on a linked list using a loop using the following steps. We are finding  item  on a linked list. Make  head  as the  current  node. Run a loop until the  current  node is  NULL  because the last element points to  NULL . In each iteration, check if the key of the node is equal to  item . If it the key matches the item, return  true  otherwise return  false . Void list:: search(){ n ode*head,* ptr , int position,count =0; { ptr = head; while ( ptr != null && ptr -> data != position){ count++; ptr = ptr -> next; } }

15. Sorting Elements of a Linked List We will use a simple sorting algorithm,  Bubble Sort , to sort the elements of a linked list in asscending order below. Make the  head  as the  current  node and create another node  index  for later use. If  head  is null, return. Else, run a loop till the last node (i.e.  NULL ). In each iteration, follow the following step 5-6. Store the next node of  current  in  index . Check if the data of the current node is greater than the next node. If it is greater, swap  current  and  index . Void list :: sorting(){ n ode* ptr ,*ptr1 ;{ Ptr =head ; While ( ptr !=NULL){ for(ptr1= ptr ->next;ptr1!=NULL;ptr1=ptr1->next){ if( ptr ->data> ptr ->data){ T= ptr -> data;ptr ->next=ptr1->data=t;}}

16. void list :: merge(){ node*ptr1,*ptr2,*ptr3;{ Ptr3=head1; ptr1=head1 ; While (ptr1->next!=NULL){ Ptr3=ptr1;ptr1= ptr ->next;ptr3=ptr3->next;} Ptr2=head2; Ptr3->next=head2;}} MERGING We need to call the  mergeSort () function. Inside the  mergeSort () function, we need to perform certain steps: First, handle the base case i.e. if the head pointer of the linked list is pointing to null then we cannot perform anything, so return. Else, we will divide the linked list into smaller halves. Now, we will sort the smaller halves of the linked list. Finally, we will merge this sorted linked list and update the head pointer pointing to the head of the merged linked list. ptr1 ptr2 Ptr3