Linked List PPT PDF

Linked List Prepared By: Dr. Asmaa Awad  Linked List A linked list is a linear data structure, in which the elements are stored in the form of a node. Each node contains two sub-elements. A data part that stores the value of the element and next part that stores the p...

Linked List Prepared By: Dr. Asmaa Awad  Linked List A linked list is a linear data structure, in which the elements are stored in the form of a node. Each node contains two sub-elements. A data part that stores the value of the element and next part that stores the pointer to the next node 2  Linked List A linked list is a linear data structure, in which the elements are stored in the form of a node. Each node contains two sub-elements. A data part that stores the value of the element and next part that stores the pointer to the next node 3  Advantages of Linked List They are dynamic in nature and allocate memory as and when required Insertion and deletion are easy to implement Other data structures such as Stack and Queue can also be implemented using a linked list It has faster access time and can be expanded in constant time without memory overhead No need to define an initial size for a linked list, hence memory utilization is effective Backtracking is possible in doubly linked lists. 4  Disadvantages of Linked List Random access is not allowed. We have to access elements sequentially starting from the first node. So, we cannot do binary search efficiently Linked lists also waste less memory for large elements (records of information). Wasted memory is memory space in the data structure not used for data. such as the pointer in each node. In arrays, the wasted memory is the part of the array not being utilized. 5  Linked List The first node also known as HEAD is always used as a reference to traverse the list. The last node points to NULL(know as tail). Linked list can be visualized as a chain of nodes, where every node points to the next node. 6  Linked List Types of Linked List The types of linked list are mentioned below: Singly Linked List: can be traversed only in forward direction. Doubly Linked List: can be traversed in forward and backward directions. Circular Singly Linked List: Last element contains link to the first element as next. Circular Doubly Linked List: Last element contains link to the first element as next and the first element contains link of the last element as previous. 7  Linked List Operations Insert node  Insert a new node at the start  Insert a new node at the end  Insert a new node at a given position Traverse linked list Search node Delete node  Delete the first node  Delete the last node  Delete a node at a given position  Delete all nodes Count nodes Reverse update 8  Insert a new node at the start Inserting a new node at the beginning of the Linked List is very easy. First, a new node with given element is created. It is then added before the head of the given Linked List that makes the newly added node to new head of the Linked List by changing the head pointer to point to the new node. 9 Insert a new node at the start 10  Traverse Linked List Traversing through a linked list is very easy. It requires creating a temp node pointing to the head of the list. If the temp node is not null, display its content and move to the next node using temp next. Repeat the process till the temp node becomes null. If the temp node is empty at the start, then the list contains no item. The function TravserseList is created for this purpose. It is a 3-step process. 11  Traverse Linked List Traversing through a linked list is very easy. It requires creating a temp node pointing to the head of the list. If the temp node is not null, display its content and move to the next node using temp next. Repeat the process till the temp node becomes null. If the temp node is empty at the start, then the list contains no item. The function TravserseList is created for this purpose. It is a 3-step process. Test Traverse 12  Insert a new node at the end Inserting a new node at the end of the Linked List is very easy. First, a new node with given element is created. It is then added at the end of the list by linking the last node to the new node. 13 Insert a new node at the end Test insertlast 14  Insert a new node at the given position First, a new node with given element is created. If the insert position is 1, then the new node is made to head. Otherwise, traverse to the node that is previous to the insert position and check if it is null or not.  In case of null, the specified position does not exist.  In other case, assign next of the new node as next of the previous node and next of previous node as new node. 15 Insert a new node at the given position Test 16  Search Element Searching an element in a linked list requires creating a temp node pointing to the head of the linked list. Along with this, two more variables are required to track search and track index of the current node. If the temp node is not null at the start, then traverse the linked list to check if current node value matches with the search value. If it matches then update search tracker variable and stop traversing the list, else keep on traversing the list. If the temp node is empty at the start, then the list contains no item. 17 Test 18  Delete the first node Deleting the first node of the linked list is very easy. If the head is not null then create a temp node pointing to head and move head to the next of head. Then delete the temp node. 19 Delete the first node Test 20  Delete the last node Deleting the last node of the Linked List involves checking the head for empty. If it is not empty, then check the head next for empty. If the head next is empty, then release the head, else traverse to the second last node of the list. Then, link the next of second last node to NULL and delete the last node. 21  Delete the last node Deleting the last node of the Linked List involves checking the head for empty. If it is not empty, then check the head next for empty. If the head next is empty, then release the head, else traverse to the second last node of the list. Then, link the next of second last node to NULL and delete the last node. 22 Delete the last node Test 23  Delete a node at the given position First, the specified position must be greater than equal to 1. If the specified position is 1 and head is not null, then make the head next as head and delete the previous head. Else, traverse to the node that is previous to the specified position. If the specified node and previous to the specified node are not null then adjust the link. In other case, the specified node will be already null. The below figure describes the process, if the deletion node is other than the head node. 24 Delete a node at the given position Test 25 26