Linked List Operations

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 reference (i.e., "next") to the next node
• Insertion and deletion operations can be performed in O(1) time, but finding a node in the list takes O(n) time
• Used in applications where frequent insertion and deletion of nodes are necessary

Doubly Linked List

• A type of linked list where each node has references to both the previous and next node in the sequence
• Each node consists of a data field, a reference to the previous node ("prev"), and a reference to the next node ("next")
• Insertion and deletion operations can be performed in O(1) time, and finding a node in the list takes O(n) time
• Used in applications where frequent insertion and deletion of nodes are necessary, and where the ability to traverse the list in both directions is important

Circular Linked List

• A type of linked list where the last node points back to the first node, forming a circle
• Used in applications where the last node needs to point back to the first node, such as in a ring buffer
• Insertion and deletion operations can be performed in O(1) time, but finding a node in the list takes O(n) time
• Can be either singly or doubly linked

Linked List Traversal

• The process of visiting each node in a linked list in a specific order
• There are two main types of traversal:
  • Iterative traversal: uses a loop to visit each node in the list
  • Recursive traversal: uses a recursive function to visit each node in the list
• Traversal can be performed in three ways:
  • Forward traversal: starts at the beginning of the list and visits each node in sequence
  • Backward traversal: starts at the end of the list and visits each node in reverse sequence
  • Random access traversal: visits nodes in a random or non-sequential order

Linked List

Types of Linked Lists

• Singly Linked List: each node has only a reference to the next node, consisting of a data field and a "next" reference.
• Doubly Linked List: each node has references to both the previous and next node, consisting of a data field, a "prev" reference, and a "next" reference.
• Circular Linked List: the last node points back to the first node, forming a circle, and can be either singly or doubly linked.

Characteristics of Linked Lists

• Singly Linked List:
  • Insertion and deletion operations: O(1) time
  • Finding a node: O(n) time
  • Used in applications with frequent insertion and deletion of nodes
• Doubly Linked List:
  • Insertion and deletion operations: O(1) time
  • Finding a node: O(n) time
  • Used in applications with frequent insertion and deletion of nodes, and traversing in both directions
• Circular Linked List:
  • Insertion and deletion operations: O(1) time
  • Finding a node: O(n) time
  • Used in applications where the last node needs to point back to the first node

Linked List Traversal

• The process of visiting each node in a linked list in a specific order
• Two main types of traversal:
  • Iterative traversal: uses a loop to visit each node
  • Recursive traversal: uses a recursive function to visit each node
• Traversal can be performed in three ways:
  • Forward traversal: starts at the beginning of the list and visits each node in sequence
  • Backward traversal: starts at the end of the list and visits each node in reverse sequence
  • Random access traversal: visits nodes in a random or non-sequential order