Data Structures: Linked Lists

Linked Lists

• A linked list is a dynamic collection of nodes, each of which contains a value and a reference (i.e., a "link") to the next node in the list.
• Advantages:
  • Efficient insertion and deletion of nodes at any position in the list.
  • Good memory usage, as nodes are allocated and deallocated as needed.
• Disadvantages:
  • Slow search times, as each node must be traversed in sequence.
  • More complex to implement than arrays.
• Types of linked lists:
  • Singly linked lists: each node only contains a reference to the next node.
  • Doubly linked lists: each node contains references to both the previous and next nodes.
  • Circularly linked lists: the last node points back to the first node.

Stacks

• A stack is a Last-In-First-Out (LIFO) data structure, meaning the most recently added item is the first to be removed.
• Operations:
  • Push: add an item to the top of the stack.
  • Pop: remove the top item from the stack.
  • Peek: view the top item without removing it.
• Uses:
  • Evaluating postfix expressions.
  • Implementing recursive algorithms.
  • Parsing syntax in compilers.
• Types of stacks:
  • Array-based stacks: using a fixed-size array to store stack elements.
  • Linked list-based stacks: using a linked list to store stack elements.

Searching Algorithms

• Linear Search
  • Iterate through a list or array one element at a time, checking if the target element is found.
  • Time complexity: O(n), where n is the number of elements in the list.
• Binary Search
  • Divide a sorted list or array in half, and search for the target element in one of the two halves.
  • Time complexity: O(log n), where n is the number of elements in the list.
  • Requires a sorted list.
• Hash Table Search
  • Use a hash function to map the target element to a specific index in a hash table.
  • Time complexity: O(1), on average, but can be O(n) in the worst case.
  • Requires a hash table data structure.

Linked Lists

• A linked list is a dynamic collection of nodes, each containing a value and a reference to the next node.
• Advantages of linked lists include efficient insertion and deletion of nodes, and good memory usage.
• Disadvantages of linked lists include slow search times, and increased complexity compared to arrays.

Types of Linked Lists

• Singly linked lists: each node contains a reference to the next node.
• Doubly linked lists: each node contains references to both the previous and next nodes.
• Circularly linked lists: the last node points back to the first node.

Stacks

• A stack is a Last-In-First-Out (LIFO) data structure, where the most recently added item is the first to be removed.
• Stack operations include push, pop, and peek.
• Stacks are used for evaluating postfix expressions, implementing recursive algorithms, and parsing syntax in compilers.

Types of Stacks

• Array-based stacks: using a fixed-size array to store stack elements.
• Linked list-based stacks: using a linked list to store stack elements.

Searching Algorithms

• Linear Search: iterate through a list or array one element at a time, checking if the target element is found.
• Time complexity of linear search: O(n), where n is the number of elements in the list.

Binary Search

• Divide a sorted list or array in half, and search for the target element in one of the two halves.
• Time complexity of binary search: O(log n), where n is the number of elements in the list.
• Binary search requires a sorted list.

Hash Table Search

• Use a hash function to map the target element to a specific index in a hash table.
• Time complexity of hash table search: O(1), on average, but can be O(n) in the worst case.
• Hash table search requires a hash table data structure.

Depth-First Search (DFS)

• Uses a stack to store nodes to visit and explores as far as possible along each branch before backtracking.
• Starts at the root node (or an arbitrary node of a graph) and visits nodes in a Last-In-First-Out (LIFO) order.
• Pseudocode involves creating a stack, popping nodes, marking them as visited, and pushing unvisited neighbors.

Breadth-First Search (BFS)

• Uses a queue to store nodes to visit and explores all nodes at the current level before moving to the next level.
• Starts at the root node (or an arbitrary node of a graph) and visits nodes in a First-In-First-Out (FIFO) order.
• Pseudocode involves creating a queue, dequeuing nodes, marking them as visited, and enqueueing unvisited neighbors.

Graph Traversal Applications

• Finding connected components in a graph
• Topological sorting
• Finding strongly connected components
• Solving puzzles and mazes
• Network topology mapping
• Web crawlers and search engines

Time and Space Complexity

• DFS: O(|E| + |V|) time complexity and O(|V|) space complexity
• BFS: O(|E| + |V|) time complexity and O(|V|) space complexity

Searching Algorithms

• DFS is useful for:
  • Very deep graphs
  • Finding a path between two nodes
• BFS is useful for:
  • Very wide graphs
  • Finding the shortest path between two nodes
• Both DFS and BFS can be used for:
  • Finding the shortest path
  • Finding all possible paths
  • Detecting cycles in a graph