Linked List Concepts

Linked List

Singly Linked List

• A type of linked list where each node only has a reference to the next node in the sequence.
• Each node consists of a data field and a next field (i.e., a reference to the next node).
• The last node in the list has a null reference in its next field, indicating the end of the list.

Doubly Linked List

• A type of linked list where each node has references to both the previous and next nodes in the sequence.
• Each node consists of a data field, a prev field (i.e., a reference to the previous node), and a next field (i.e., a reference to the next node).
• The first node in the list has a null prev field, and the last node has a null next field.

Circularly Linked List

• A type of linked list where the last node points back to the first node, forming a circle.
• Each node consists of a data field and a next field (i.e., a reference to the next node).
• There is no null reference in the list, as the last node points back to the first node.

Linked List Implementation

• A linked list can be implemented using a Node class, which has a data field and a reference to the next node.
• The linked list class itself can have methods for inserting, deleting, and traversing the list.
• The implementation can be done recursively or iteratively.

Linked List Traversal

• Traversal methods:
  • Iterative traversal: uses a loop to traverse the list.
  • Recursive traversal: uses a recursive function to traverse the list.
• Traversal operations:
  • Insertion: adding a new node to the list.
  • Deletion: removing a node from the list.
  • Searching: finding a specific node in the list.
  • Printing: displaying the contents of the list.
• Time complexity:
  • Insertion: O(1) at the beginning or end, O(n) at a specific position.
  • Deletion: O(1) at the beginning or end, O(n) at a specific position.
  • Searching: O(n) in the worst case.
  • Printing: O(n) in the worst case.

Linked List

Singly Linked List

• Each node has a data field and a reference to the next node.
• The last node has a null reference, indicating the end of the list.

Doubly Linked List

• Each node has references to both the previous and next nodes.
• Each node consists of a data field, a prev field, and a next field.
• The first node has a null prev field, and the last node has a null next field.

Circularly Linked List

• The last node points back to the first node, forming a circle.
• Each node consists of a data field and a next field.
• There is no null reference in the list.

Implementation

• A Node class has a data field and a reference to the next node.
• The linked list class has methods for inserting, deleting, and traversing the list.
• Implementation can be done recursively or iteratively.

Traversal

Traversal Methods

• Iterative traversal uses a loop to traverse the list.
• Recursive traversal uses a recursive function to traverse the list.

Traversal Operations

• Insertion adds a new node to the list.
• Deletion removes a node from the list.
• Searching finds a specific node in the list.
• Printing displays the contents of the list.

Time Complexity

• Insertion is O(1) at the beginning or end, O(n) at a specific position.
• Deletion is O(1) at the beginning or end, O(n) at a specific position.
• Searching is O(n) in the worst case.
• Printing is O(n) in the worst case.