YouTipDsa Linear Data Structures
## Linear Data Structures\\n\\nIn this chapter, we will introduce the most basic and commonly used category of data structures - **linear data structures**.\\n\\n**Linear data structures** resemble people standing in a queue:\\n\\n* Each person (element) has a clear before-and-after relationship\\n* Except for the first and last, each has one predecessor and one successor\\n* Data elements have a one-to-one linear relationship\\n\\n> Imagine you're queuing to buy coffee or organizing books on a shelf.\\n> \\n> \\n> These scenarios share a commonality: elements are arranged one after another, forming a line.\\n> \\n> \\n> In computer science, this ordered data collection constitutes a linear data structure.\\n> \\n> \\n> The characteristic of linear data structures is: except for the first and last elements, every element has exactly one **predecessor** and one **successor**.\\n\\n**Common Linear Data Structures:**\\n\\n1. **Array**: Resembles numbered lockers with fixed positions\\n2. **Linked List**: Resembles people holding hands, each remembering only adjacent people\\n3. **Stack**: Resembles stacked plates that can only be added/removed from the top\\n4. **Queue**: Resembles a ticket queue following first-come-first-serve principles\\n\\nThe following diagram shows the classification system for linear data structures, each with specific application scenarios and performance characteristics:\\n\\n!(#)\\n\\nThe following diagram illustrates the basic operations of a stack, which follows LIFO (Last In First Out) principle:\\n\\n!(#)\\n\\n### Array (Array)\\n\\n#### Static Array\\n\\n| Feature | Description | Time Complexity |\\n| --- | --- | --- |\\n| Access Element | Direct access via index | O(1) |\\n| Insert Element | Requires shifting subsequent elements | O(n) |\\n| Delete Element | Requires shifting subsequent elements | O(n) |\\n| Space Allocation | Fixed size, pre-allocated | O(1) |\\n\\n#### Dynamic Array\\n\\n| Feature | Description | Time Complexity |\\n| --- | --- | --- |\\n| Access Element | Direct access via index | O(1) |\\n| Insert Element | May require expansion and copying | Average O(1), Worst O(n) |\\n| Delete Element | Requires shifting subsequent elements | O(n) |\\n| Space Allocation | Automatic expansion | O(n) (upon expansion) |\\n\\n### Linked List (Linked List)\\n\\n#### Singly Linked List\\n\\n| Operation | Description | Time Complexity |\\n| --- | --- | --- |\\n| Access Element | Requires traversal from head | O(n) |\\n| Insert at Head | Direct insertion | O(1) |\\n| Insert at Tail | Requires traversal to tail | O(n) |\\n| Insert in Middle | Requires finding position first | O(n) |\\n| Delete Element | Requires finding position first | O(n) |\\n\\n#### Doubly Linked List\\n\\n| Operation | Description | Time Complexity |\\n| --- | --- | --- |\\n| Access Element | Requires traversal from head/tail | O(n) |\\n| Insert at Head | Direct insertion | O(1) |\\n| Insert at Tail | Direct insertion (with tail pointer) | O(1) |\\n| Insert in Middle | Requires finding position first | O(n) |\\n| Delete Element | Requires finding position first | O(n) |\\n\\n### Stack (Stack)\\n\\n| Operation | Description | Time Complexity |\\n| --- | --- | --- |\\n| push(push) | Add element at stack top | O(1) |\\n| pop(pop) | Remove stack top element | O(1) |\\n| peek(peek) | View stack top element | O(1) |\\n| isEmpty(isEmpty) | Check if stack is empty | O(1) |\\n\\n### Queue (Queue)\\n\\n| Operation | Description | Time Complexity |\\n| --- | --- | --- |\\n| enqueue(enqueue) | Add element at tail | O(1) |\\n| dequeue(dequeue) | Remove head element | O(1) |\\n| front(front) | View head element | O(1) |\\n| isEmpty(isEmpty) | Check if queue is empty | O(1) |\\n\\n* * *\\n\\n### Linear Data Structures Comparison Chart\\n\\n* * *\\n\\n## Array: The Fixed Apartment Building for Data\\n\\nThe array is the simplest and most direct linear data structure.\\n\\nWe can visualize it as an **apartment building with fixed floors**.\\n\\n### Basic Concepts and Characteristics\\n\\n* **Contiguous Storage**: Arrays occupy a **contiguous** block of memory, like rooms adjacent in an apartment building.\\n* **Fixed Size**: The array's capacity (length) must be determined upon creation and usually cannot be changed afterward, just as room numbers become fixed after construction.\\n* **Indexed Access**: Each element (room) has a unique number called an **index**. In most programming languages, indices start from `0`. You can directly and quickly access any element via its index with `O(1)` time complexity.\\n\\n### Core Operations and Code Examples\\n\\nLet's demonstrate core array operations using Python (Note: Python's `list` is dynamic and commonly used for arrays).\\n\\n## Example\\n\\n# 1. Create Array\\n\\n apartment_building =['101Room-Zhang San','102Room-Li Si','103Room-Wang Wu','104Room-Empty','105Room-Empty']\\n\\nprint("Apartments:", apartment_building)\\n\\n# 2. Access Element (via index)\\n\\n# Access 102 room\\n\\n tenant = apartment_building # Index starts at 0, so 1 corresponds to second element\\n\\nprint(f"Tenant in 102: {tenant}")\\n\\n# 3. Update Element\\n\\n# New tenant Zhao Liu moved into 104 room\\n\\n apartment_building= '104Room-Zhao Liu'\\n\\nprint("After Zhao Liu moved in:", apartment_building)\\n\\n# 4. Insert Element (Efficient at end, simulating "expansion")\\n\\n# Supposedly add room 106 at the end\\n\\n apartment_building.append('106Room-Sun Qi')\\n\\nprint("After adding room 106:", apartment_building)\\n\\n# 5. Delete Element\\n\\n# Wang Wu moves out of room 103\\n\\n# Method 1: Mark as vacant (logical delete)\\n\\n# apartment_building = '103Room-Empty'\\n\\n# Method 2: Remove element, subsequent elements shift (physical delete, less efficient)\\n\\n removed_tenant = apartment_building.pop(2) # Remove element at index 2\\n\\nprint(f"{removed_tenant} moved out.")\\n\\nprint("After Wang Wu moved out:", apartment_building)\\n\\nOutput:\\n\\nApartments: ['101Room-Zhang San','102Room-Li Si','103Room-Wang Wu','104Room-Empty','105Room-Empty']Tenant in 102: 102Room-Li SiAfter Zhao Liu moved in: ['101Room-Zhang San','102Room-Li Si','103Room-Wang Wu','104Room-Zhao Liu','105Room-Empty']After adding room 106: ['101Room-Zhang San','102Room-Li Si','103Room-Wang Wu','104Room-Zhao Liu','105Room-Empty','106Room-Sun Qi']103Room-Wang Wu moved out.After Wang Wu moved out: ['101Room-Zhang San','102Room-Li Si','104Room-Zhao Liu','105Room-Empty','106Room-Sun Qi']\\n\\n### Advantages and Disadvantages\\n\\n| Advantages | Disadvantages |\\n| --- | --- |\\n| **High-speed Random Access**: Access any element in constant time via index. | **Fixed Size**: Static arrays are difficult to resize after creation. |\\n| **High Memory Efficiency**: Contiguous storage requires no extra space for element relationships. | **High Insertion/Deletion Cost**: Inserting/deleting in the middle requires shifting subsequent elements to maintain continuity. |\\n\\n* * *\\n\\n## Linked List: The Treasure Train of Data\\n\\nLinked lists address the issues of fixed size and inefficient insertion/deletion in arrays. A linked list resembles a **train**, where each carriage (node) carries cargo (data) and connects to the next carriage via a hook (pointer).\\n\\n### Basic Concepts and Types\\n\\nEach **node** in a linked list contains at least two parts:\\n\\n1. **Data Field**: Stores actual data values.\\n2. **Pointer Field**: Stores the memory address of the next node.\\n\\n!(#)\\n\\nThe diagram above shows a **singly linked list** structure. The head pointer points to the first node. Each node's `Next` points to the next node. The last node's `Next` points to `NULL`, indicating the end.\\n\\nMain linked list types:\\n\\n* **Singly Linked List**: Nodes point only to the next node.\\n* **Doubly Linked List**: Nodes point to both previous and next nodes, enabling bidirectional traversal.\\n* **Circular Linked List**: The tail node points back to the head node, forming a loop.\\n\\n### Core Operations and Code Examples\\n\\nLet's implement a basic singly linked list.\\n\\n## Example\\n\\nclass ListNode:\\n\\n"""Define linked list node class"""\\n\\ndef __init__ (self, data):\\n\\nself.data= data # Data field\\n\\nself.next=None # Pointer field, initially points to None\\n\\nclass LinkedList:\\n\\n"""Define singly linked list class"""\\n\\ndef __init__ (self):\\n\\nself.head=None # Head pointer\\n\\ndef append(self, data):\\n\\n"""Append node at list tail"""\\n\\n new_node = ListNode(data)\\n\\nif not self.head: # If list empty, new node becomes head\\n\\nself.head= new_node\\n\\nreturn\\n\\n last_node =self.head\\n\\nwhile last_node.next: # Traverse to last node\\n\\n last_node = last_node.next\\n\\n last_node.next= new_node # Append new node\\n\\ndef prepend(self, data):\\n\\n"""Prepend node at list head"""\\n\\n new_node = ListNode(data)\\n\\n new_node.next=self.head\\n\\nself.head= new_node\\n\\ndef delete(self, key):\\n\\n"""Delete first node with value key"""\\n\\n current_node =self.head\\n\\n# If deleting head node\\n\\nif current_node and current_node.data== key:\\n\\nself.head= current_node.next\\n\\n current_node =None\\n\\nreturn\\n\\nprev_node =None\\n\\n# Traverse to find target node\\n\\nwhile current_node and current_node.data!= key:\\n\\n prev_node = current_node\\n\\n current_node = current_node.next\\n\\nif current_node is None: # Not found\\n\\nreturn\\n\\n# Found it, skip node via pointer reassignment\\n\\n prev_node.next= current_node.next\\n\\n current_node =None\\n\\ndef print_list(self):\\n\\n"""Print all list elements"""\\n\\n current_node =self.head\\n\\nwhile current_node:\\n\\nprint(current_node.data, end=" -> ")\\n\\n current_node = current_node.next\\n\\nprint("NULL")\\n\\n# Test linked list\\n\\nprint("=== Singly Linked List Demo ===")\\n\\n train = LinkedList()\\n\\n train.append("Carriage1-Coal")\\n\\n train.append("Carriage2-Wood")\\n\\n train.prepend("Locomotive")# Insert at head\\n\\n train.append("Carriage3-Steel")\\n\\nprint("Initial train:")\\n\\n train.print_list()# Output: Locomotive -> Carriage1-Coal -> Carriage2-Wood -> Carriage3-Steel -> NULL\\n\\ntrain.delete("Carriage2-Wood")\\n\\nprint("After unloading wood:")\\n\\n train.print_list()# Output: Locomotive -> Carriage1-Coal -> Carriage3-Steel -> NULL\\n\\nOutput:\\n\\n=== Singly Linked List Demo ===Initial train:Locomotive -> Carriage1-Coal -> Carriage2-Wood -> Carriage3-Steel -> NULLAfter unloading wood:Locomotive -> Carriage1-Coal -> Carriage3-Steel -> NULL\\n\\n### Advantages and Disadvantages\\n\\n| Advantages | Disadvantages |\\n| --- | --- |\\n| **Dynamic Size**: No pre-allocated fixed space; can flexibly grow/shrink. | **Memory Overhead**: Each node requires extra pointer storage space. |\\n| **Efficient Insertion/Deletion**: Known node locations require only pointer modification, no mass element shifting. | **Sequential Access**: Cannot access via index like arrays; must traverse from head. |\\n| | **Cache Unfriendly**: Nodes scattered in memory, hindering CPU cache prefetching. |\\n\\n* * *\\n\\n## Stack: The Stacked Dishes of Data\\n\\nStack is a **LIFO (Last In First Out)** data structure, resembling stacked dishes in a restaurant where you always remove the topmost one (last placed).\\n\\n### Basic Concepts and Operations\\n\\nStack only allows insertion (**Push**) and deletion (**Pop**) operations at one end (**Stack Top**). The opposite end is the **Stack Bottom**.\\n\\nCore Operations:\\n\\n* **push(data)**: Pushes data onto stack top.\\n* **pop()**: Pops and returns stack top element.\\n* **peek() / top()**: Views stack top element without popping.\\n* **is_empty()**: Checks if stack is empty.\\n\\n!(#)\\n\\n### Application Scenarios and Code Examples\\n\\nStacks are widely used in computer science: function call stacks, browser navigation history, expression evaluation, bracket matching, etc.\\n\\n## Example\\n\\nclass Stack:\\n\\n"""Implement stack using list"""\\n\\ndef __init__ (self):\\n\\nself.items=[]\\n\\ndef push(self, item):\\n\\n"""Push item"""\\n\\nself.items.append(item) # List end as stack top\\n\\ndef pop(self):\\n\\n"""Pop item, return None if stack empty"""\\n\\nif not self.is_empty():\\n\\nreturn self.items.pop()\\n\\nreturn None\\n\\ndef peek(self):\\n\\n"""View stack top"""\\n\\nif not self.is_empty():\\n\\nreturn self.items\\n\\nreturn None\\n\\ndef is_empty(self):\\n\\n"""Check if stack empty"""\\n\\nreturn len(self.items)==0\\n\\ndef size(self):\\n\\n"""Return stack size"""\\n\\nreturn len(self.items)\\n\\n# Application: Parentheses Matching Check\\n\\ndef is_balanced_parentheses(expression):\\n\\n"""\\n\\n Check if parentheses in expression match\\n\\n E.g., (()) balanced, (() unbalanced\\n\\n """\\n\\n stack = Stack()\\n\\n# Parenthesis matching map\\n\\n matching_bracket ={')': '(',']': '[','}': '{'}\\n\\nfor char in expression:\\n\\nif char in '([{' : # Open bracket, push\\n\\n stack.push(char)\\n\\nelif char in ')]}' : # Closing bracket\\n\\nif stack.is_empty():\\n\\nreturn False # Stack empty means excess closing brackets\\n\\n top_char = stack.pop()\\n\\nif matching_bracket!= top_char : # Check match\\n\\nreturn False\\n\\n# After loop, stack should be empty\\n\\nreturn stack.is_empty()\\n\\n# Test stack and parentheses matching\\n\\nprint("n=== Stack and Parentheses Matching Demo ===")\\n\\n plate_stack = Stack()\\n\\n plate_stack.push("Plate1")\\n\\n plate_stack.push("Plate2")\\n\\n plate_stack.push("Plate3")\\n\\nprint(f"Remove top plate: {plate_stack.pop()}")# Output: Plate3\\n\\nprint(f"Current top plate: {plate_stack.peek()}")# Output: Plate2\\n\\n# Test parentheses matching\\n\\n test_cases =["((1+2)*3)","({})","((())",")( )"]\\n\\nfor test in test_cases:\\n\\n result ="Balanced" if is_balanced_parentheses(test) else "Unbalanced"\\n\\nprint(f"Expression '{test}' has {result} parentheses.")\\n\\nOutput:\\n\\n=== Stack and Parentheses Matching Demo ===Remove top plate: Plate3Current top plate: Plate2Expression '((1+2)*3)' has Balanced parentheses.Expression '({})' has Balanced parentheses.Expression '((())' has Unbalanced parentheses.Expression ')( )' has Unbalanced parentheses.\\n\\n* * *\\n\\n## Queue: The Waiting Queue for Data\\n\\nQueue is an **FIFO (First In First Out)** data structure, resembling any real-life queue system (like supermarket checkouts), where the first arrival receives service first.\\n\\n### Basic Concepts and Operations\\n\\nQueue allows adding elements at one end (**Rear**) and removing them from the other end (**Front**).\\n\\nCore Operations:\\n\\n* **enqueue(data)**: Adds element at rear.\\n* **dequeue()**: Removes and returns element from front.\\n* **front()**: Returns front element.\\n* **isEmpty()**: Checks if queue is empty.\\n* **size()**: Returns queue size.