Linked List

1. Singly Linked List

• Singly linked list is a linear data structure which is a collection of nodes at different memory locations linked together to store data.This create a flexible way to store and organize data.
• Node is consist of two fields
  • Data : Stores the element.
  • Pointer : Stores the address(pointer) to the next node.
• Head points to the first node of the linked list while the last node’s pointer containing a null value to indicate the current linked list end.
• This will increase the flexibility of organizing and storing of the data in the linked list.

UML class diagram of a node

Structure of a linked list

UML classs diagram of a linked list

1.2 Types of linked lists

• Singly Linked List : each node points to the next node in a sequence.
• Doubly Linked List : each node contains a pointer to both the next node and previous node. This helps to traverse in both ways.
• Circular Linked List : In this last node’s pointer refers to the first node.

1.3 Operations on linked lists

1. Insertion
   • Insert at the start : This can be acquired by adding a new node to the start of the linked list by updating only the head pointer.
   • Insert at the end : This can be acquired by traversing to the last node and then updating the references of the new node to the last node.
   • Insert at given position : This can be acquired by traversing to the user defined position and then updating the references of the new node.
2. Deletion
   • Delete at the start : This can be acquired by deleting a new node from the start of the linked list by updating only the head pointer to the second node.
     
   • Delete at the end : This can be acquired by traversing to the last node and then updating the references of the last node to the previous last node.
     
   • Delete at given position : This can be acquired by traversing to the user defined data and then updating the references of the specific node to the previous node.
     
3. Traversal
   • Forward traversal : Starting from the head node reaching every node in a forward sequence.
     
   • Backward traversal : Starting from the last node and reaching ecery node in a backward sequence.
4. Searching
   • search for a data iterating throug the linked list until the conditioned data is met.
     
5. Printing Linked List
   • print every element after iterating through the linked list.
     

1.3 Applications of linked lists

• Dynamic memory allocation : Linked lists are frequently used to efficiently manage memory and allocate memory blocks as needed.
• Implementing stacks and queues : Used in implementing Stack and Queue data structure.By blocking unwanted access or change, access modifiers help in protecting the data inside an object.
• Undo / Redo : Used in software applications to provide undo and redo functions, which allow users to return back activities.