Data Structures Unit 2 ReviewArrays and Linked Lists

What Are Arrays and Linked Lists?

• Arrays store elements of the same data type in contiguous memory locations
  • Enables efficient element access using an index
  • Fixed size determined at creation time
• Linked lists consist of nodes containing data and references to other nodes
  • Nodes can be scattered in memory
  • Size can change dynamically during runtime
• Both arrays and linked lists are used to store collections of related data
• Arrays have a fixed size, while linked lists can grow or shrink as needed
• Elements in an array are accessed using an index, while linked list elements are accessed by traversing the list
• Arrays and linked lists form the basis for more complex data structures (stacks, queues, hash tables)

Array Basics

• Arrays are a fundamental data structure in most programming languages
• Declare an array by specifying the data type and size int arr[5];
• Access elements using zero-based indexing arr[0] = 10;
• Array size is fixed and cannot be changed after declaration
  • Size must be known at compile time or dynamically allocated
• Arrays can be one-dimensional (1D) or multi-dimensional (2D, 3D, etc.)
  • 2D arrays are often used to represent matrices or grids
• Arrays have a constant time complexity for accessing elements by index $O(1)$
• Inserting or deleting elements in the middle of an array requires shifting elements $O(n)$

Linked List Fundamentals

• Linked lists are composed of nodes, each containing data and a reference (link) to the next node
• The first node is called the head, and the last node points to null or None
• Linked lists can be singly-linked (each node has a reference to the next node) or doubly-linked (nodes have references to both the next and previous nodes)
• Nodes can be inserted or deleted by updating the references between nodes
  • No need to shift elements like in arrays
• Traversing a linked list requires following the references from node to node $O(n)$
  • No direct access to elements by index like in arrays
• Linked lists can grow or shrink dynamically during runtime
• Memory usage is higher compared to arrays due to the storage of references

Comparing Arrays and Linked Lists

• Arrays have a fixed size, while linked lists can grow or shrink dynamically
• Arrays have contiguous memory allocation, while linked list nodes can be scattered in memory
• Accessing elements in an array by index is efficient $O(1)$, while accessing elements in a linked list requires traversal $O(n)$
• Inserting or deleting elements in the middle of an array is inefficient $O(n)$ due to shifting, while linked lists can efficiently insert or delete nodes by updating references $O(1)$
• Arrays have better cache locality due to contiguous memory, resulting in faster iteration
• Linked lists have higher memory overhead due to storing references along with data
• Arrays are better for scenarios with frequent random access, while linked lists are better for scenarios with frequent insertions or deletions in the middle

Common Operations and Time Complexity

• Accessing an element by index:
  • Array: $O(1)$
  • Linked List: $O(n)$
• Inserting or deleting an element at the beginning:
  • Array: $O(n)$ (requires shifting elements)
  • Linked List: $O(1)$
• Inserting or deleting an element in the middle:
  • Array: $O(n)$ (requires shifting elements)
  • Linked List: $O(n)$ (requires traversal to find the insertion/deletion point)
• Searching for an element:
  • Array: $O(n)$ (linear search), $O(log n)$ (binary search, if sorted)
  • Linked List: $O(n)$
• Updating an element:
  • Array: $O(1)$ (direct access by index)
  • Linked List: $O(n)$ (requires traversal to find the element)

Implementing Arrays and Linked Lists

• Arrays can be implemented using static or dynamic memory allocation
  • Static allocation: int arr[10];
  • Dynamic allocation: int* arr = new int[10];
• Linked lists are implemented using dynamic memory allocation for each node
  • Each node contains data and a reference to the next node

  </>C++
  struct Node {
      int data;
      Node* next;
  };

• Linked list operations involve updating references between nodes
  • Insertion: create a new node and update the references to include it in the list
  • Deletion: update the references to bypass the node to be deleted and free its memory
• Implementing linked lists requires careful memory management to avoid leaks
  • Deallocate memory for nodes that are no longer needed

Real-World Applications

• Arrays:
  • Storing and accessing large amounts of data (databases, file systems)
  • Implementing other data structures (stacks, queues, hash tables)
  • Representing matrices and grids (image processing, game boards)
• Linked Lists:
  • Implementing other data structures (stacks, queues, hash tables)
  • Representing dynamic collections of data (playlists, undo/redo functionality)
  • Memory management (operating systems, memory allocators)
• Both arrays and linked lists are used extensively in system design and algorithms
  • Choosing the appropriate data structure depends on the specific requirements and trade-offs of the problem at hand

Practice Problems and Exercises

• Implement a function to reverse an array in-place
• Implement a function to find the maximum subarray sum in an array
• Implement a function to remove duplicates from a sorted array
• Implement a singly-linked list with methods for insertion, deletion, and traversal
• Implement a function to reverse a singly-linked list
• Implement a function to detect and remove a loop in a linked list
• Solve the "Two Sum" problem using an array and a hash table
• Implement a linked list-based queue and stack
• Solve the "Merge Two Sorted Lists" problem using linked lists