Data Structures: Lists

Cheatsheet Content

### Lists A list is a sequence of elements with a fixed order. - Elements can be added, removed, inspected, and updated anywhere. This makes lists more general than stacks or queues. - The length of a list is the number of elements it contains. - An empty list has a length of zero. - Lists can be implemented using both arrays and linked lists. ### List as an Abstract Data Type (ADT) - The **List ADT** is a sequential collection of elements that supports a set of operations without specifying the internal implementation. - It provides an ordered way to store, access, and modify data. ### List Operations | Operation | Description | |--------------------|-----------------------------------| | `create()` | Create an empty list | | `insert(pos, item)`| Insert item at a specific position| | `delete(pos)` | Delete item from a specific position| | `retrieve(pos)` | Get item at a specific position | | `size()` | Returns the number of elements | | `isEmpty()` | Check if the list is empty | | `isFull()` | Check if the list is full | | `display()` | Display list elements | ### Array-Based List Algorithms #### Insert an Element ``` IF size == MAX PRINT "List is full" EXIT END IF FOR i = size TO position (Downto) list[i] = list[i-1] END FOR list[position] = item size = size + 1 ``` #### Delete an Element ``` IF size == 0 PRINT "List is empty" EXIT END IF FOR i = position TO size-1 list[i] = list[i+1] END FOR size = size - 1 ``` #### Display All Elements ``` FOR i = 0 TO size-1 PRINT list[i] END FOR ``` ### Array-Based List C Example ```c #include #define MAX 100 int list[MAX]; int size = 0; void insert(int item, int pos) { if (size == MAX) { printf("List is full\n"); return; } for (int i = size; i > pos; i--) { list[i] = list[i - 1]; } list[pos] = item; size++; } void delete(int pos) { if (size == 0) { printf("List is empty\n"); return; } for (int i = pos; i ### Structure and Pointer (C Language) #### Declaring a Pointer to a Structure - Syntax: `struct struct_name *ptr;` - Example: `struct student *ptr_stud, stud;` #### Assigning Address to a Structure Pointer - To assign the address of a structure variable (`stud`) to a pointer (`ptr_stud`): - `ptr_stud = &stud;` #### Accessing Members via Structure Pointer - **Direct access (using `*` and `.` operators):** - `(*ptr_stud).roll_no;` (Parentheses are crucial due to operator precedence) - **Using the `->` (pointing-to) operator:** - C provides the `->` operator for convenience: - `ptr_stud -> roll_no = 01;` ### Structure and Pointer C Example ```c #include struct Student { int roll; char name[25]; }; void display(struct Student *obj_st) { printf("Your roll number is %d\n", (*obj_st).roll); printf("Your name is %s\n", (*obj_st).name); } int main() { struct Student s, *st; st = &s; printf("Enter name: "); scanf("%s", &(*st).name); // or st->name printf("Enter roll: "); scanf("%d", &(*st).roll); // or &st->roll display(st); return 0; } ``` ### Self-Referential Structures - **Definition:** Structures that contain a reference (pointer) to data of their own type. - **Purpose:** Allows linking instances of the same structure together, forming dynamic data structures. - **Example:** ```c struct node { int info; // Data part struct node *next; // Pointer to the next node of the same type }; ``` - **Use Cases:** Essential for implementing linked lists, trees, and graphs. ### Linked Lists: Introduction - **Drawbacks of Sequential Storage (Arrays) for Stacks/Queues:** - Fixed amount of storage allocated. - Limited by fixed size, leading to potential overflow. - **Linked List Definition:** A dynamic data structure where each element (called a **node**) contains: 1. An **information field** (data). 2. A **next address field** (pointer) to the next item in the list. - **Pointer:** The address used to access a particular node. - **Accessing the List:** The entire linked list is typically accessed from an external pointer (often called `list` or `start`) that points to the first node. - **End of List:** The `next` address field of the last node contains a special value (usually `NULL`) to signal the end of the list. - **Empty List:** A list with no nodes is called an empty list or null list. Its external pointer is `NULL`. ### Memory Representation (Singly Linked List) Linked lists can be represented in memory using two parallel arrays: one for `Data` and one for `Next` (pointers/indices). - `START` points to the index of the first node. - `Next` field stores the index of the subsequent node. - `-1` typically indicates `NULL` (end of list). ### Singly Linked List C Example ```c #include #include // For NULL struct Node { int data; struct Node *next; }; int main() { struct Node n1, n2, n3, n4; struct Node *start; // Initialize data for nodes n1.data = 10; n2.data = 20; n3.data = 30; n4.data = 40; // Link nodes n1.next = &n2; n2.next = &n3; n3.next = &n4; n4.next = NULL; // Last node points to NULL // Initialize list start start = &n1; // Display list (Forward traversal) printf("Forward traversal: "); struct Node *temp = start; while (temp != NULL) { printf("%d -> ", temp->data); temp = temp->next; } printf("NULL\n"); return 0; } ``` ### Types of Linked List 1. **Singly Linked List** 2. **Doubly Linked List** 3. **Circular Linked List** ### Operations on Linked List 1. **Insertion:** Insert a new node. - At the beginning - At the end - At a specific position 2. **Deletion:** Delete a node. - From the beginning - From the end - From a specified position 3. **Traversing:** Accessing nodes in order to process them. 4. **Searching:** Finding an element. ### Singly Linked List - **Simplest Type:** Each node contains data and a pointer to the next node of the same data type. - **Pointer Storage:** The node's pointer stores the memory address of the next node in sequence. - **Traversal:** Data can only be traversed in one direction (forward). ### Inserting a Node at the Beginning (Singly Linked List) #### Algorithm 1. `NEW_NODE = malloc(sizeof(node))` 2. `NEW_NODE->DATA = VAL` 3. `NEW_NODE->NEXT = START` 4. `START = NEW_NODE` 5. `EXIT` #### Visual Representation ### Inserting a Node at the End (Singly Linked List) #### Algorithm 1. `NEW_NODE = malloc(sizeof(node))` 2. `SET NEW_NODE->DATA = VAL` 3. `SET NEW_NODE->NEXT = NULL` 4. `IF START = NULL` - `SET START = NEW_NODE` - `EXIT` 5. `SET PTR = START` 6. `WHILE PTR->NEXT != NULL` - `PTR = PTR->NEXT` 7. `SET PTR->NEXT = NEW_NODE` 8. `EXIT` #### Visual Representation ### Inserting a Node at a Specified Position (Singly Linked List) #### Algorithm 1. `NEW_NODE = malloc(sizeof(node))` 2. `SET NEW_NODE->DATA = VAL` 3. `SET PTR = START` 4. `FOR i = 1 TO POS-1` - `PTR = PTR->NEXT` 5. `SET NEW_NODE->NEXT = PTR->NEXT` 6. `SET PTR->NEXT = NEW_NODE` 7. `EXIT` ### Deleting the First Node (Singly Linked List) #### Algorithm 1. `SET PTR = START` 2. `SET START = START->NEXT` 3. `FREE PTR` (Deallocate memory) 4. `EXIT` #### Visual Representation ### Deleting the Last Node (Singly Linked List) #### Algorithm 1. `IF START = NULL` - `Write UNDERFLOW` - `Go to Step 8` 2. `SET PTR = START` 3. `Repeat Steps 4 and 5 while PTR->NEXT != NULL` - `SET PREPTR = PTR` - `SET PTR = PTR->NEXT` 4. `SET PREPTR->NEXT = NULL` 5. `FREE PTR` 6. `EXIT` #### Visual Representation ### Deleting a Node at a Specified Position (Singly Linked List) #### Algorithm 1. `IF START = NULL` - `Write UNDERFLOW` - `Go to Step 10` 2. `SET PTR = START` 3. `SET PREPTR = PTR` 4. `Repeat Steps 5 and 6 until position-1 is reached` - `SET PREPTR = PTR` - `SET PTR = PTR->NEXT` 5. `SET TEMP = PTR` 6. `SET PREPTR->NEXT = PTR->NEXT` 7. `FREE TEMP` 8. `EXIT` #### Visual Representation ### Doubly Linked Lists - **Definition:** A more complex type of linked list where each node contains: 1. Data 2. A pointer to the **next** node. 3. A pointer to the **previous** node. - **Structure:** ```c struct node { struct node *prev; // Pointer to the previous node int data; struct node *next; // Pointer to the next node }; ``` - **`prev` and `next` for boundary nodes:** - The `prev` field of the first node and the `next` field of the last node will contain `NULL`. - **Advantage:** The `prev` field allows traversal in the backward direction. - **Features:** - Requires more space per node and more expensive basic operations compared to singly linked lists. - Provides easier manipulation (insertion/deletion) as it maintains pointers in both directions. - Searching can be twice as efficient (can start from both ends). ### Memory Representation (Doubly Linked List) Similar to singly linked lists, but with an additional array for `Prev` pointers/indices. ### Doubly Linked List C Example ```c #include #include // For NULL and malloc struct node { int data; struct node *prev; struct node *next; }; int main() { struct node n1, n2, n3, n4, n5; struct node *start; // Initialize data n1.data = 10; n2.data = 20; n3.data = 30; n4.data = 40; n5.data = 50; // Linking nodes n1.prev = NULL; n1.next = &n2; n2.prev = &n1; n2.next = &n3; n3.prev = &n2; n3.next = &n4; n4.prev = &n3; n4.next = &n5; n5.prev = &n4; n5.next = NULL; // Start points to first node start = &n1; // Forward traversal printf("Forward traversal: "); struct node *temp = start; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("NULL\n"); // Backward traversal (starting from the last node) printf("Backward traversal: "); temp = &n5; // Point temp to the last node while (temp != NULL) { printf("%d ", temp->data); temp = temp->prev; } printf("NULL\n"); return 0; } ``` ### Inserting a Node at the Beginning (Doubly Linked List) #### Algorithm 1. `NEW_NODE = (node *) malloc(sizeof(node))` 2. `IF NEW_NODE == NULL` - `WRITE OVERFLOW` - `EXIT` 3. `SET NEW_NODE->DATA = VAL` 4. `SET NEW_NODE->PREV = NULL` 5. `SET NEW_NODE->NEXT = START` 6. `IF START != NULL` - `SET START->PREV = NEW_NODE` 7. `SET START = NEW_NODE` 8. `EXIT` #### Visual Representation ### Inserting a Node at the End (Doubly Linked List) #### Algorithm 1. `NEW_NODE = (node *) malloc(sizeof(node))` 2. `SET NEW_NODE->DATA = VAL` 3. `SET NEW_NODE->PREV = NULL` 4. `SET NEW_NODE->NEXT = NULL` 5. `IF START = NULL` - `SET START = NEW_NODE` - `EXIT` 6. `SET PTR = START` 7. `WHILE PTR->NEXT != NULL` - `PTR = PTR->NEXT` 8. `SET PTR->NEXT = NEW_NODE` 9. `SET NEW_NODE->PREV = PTR` 10. `EXIT` #### Visual Representation ### Inserting a Node at a Specified Position (Doubly Linked List) #### Algorithm 1. `NEW_NODE = (node *) malloc(sizeof(node))` 2. `SET NEW_NODE->DATA = VAL` 3. `SET PTR = START` 4. `FOR i = 1 TO POS-1` - `PTR = PTR->NEXT` 5. `SET NEW_NODE->NEXT = PTR->NEXT` 6. `SET NEW_NODE->PREV = PTR` 7. `IF PTR->NEXT != NULL` - `SET PTR->NEXT->PREV = NEW_NODE` 8. `SET PTR->NEXT = NEW_NODE` 9. `EXIT` #### Visual Representation ### Deleting the First Node (Doubly Linked List) #### Algorithm 1. `IF START = NULL` - `Write UNDERFLOW` - `Go to Step 6` 2. `SET PTR = START` 3. `SET START = START->NEXT` 4. `IF START != NULL` - `SET START->PREV = NULL` 5. `FREE PTR` 6. `EXIT` #### Visual Representation ### Deleting the Last Node (Doubly Linked List) #### Algorithm 1. `IF START = NULL` - `Write UNDERFLOW` - `Go to Step 7` 2. `SET PTR = START` 3. `While PTR->NEXT != NULL` - `SET PTR = PTR->NEXT` 4. `IF PTR->PREV != NULL` - `SET PTR->PREV->NEXT = NULL` 5. `FREE PTR` 6. `EXIT` #### Visual Representation ### Deleting a Node at a Specified Position (Doubly Linked List) #### Algorithm 1. `IF START = NULL` - `Write UNDERFLOW` - `Go to Step 9` 2. `SET PTR = START` 3. `FOR i = 1 TO POS-1` - `PTR = PTR->NEXT` 4. `IF PTR == NULL` (Position out of bounds) - `Write "Position not found"` - `EXIT` 5. `SET TEMP = PTR` 6. `IF PTR->PREV != NULL` - `SET PTR->PREV->NEXT = PTR->NEXT` 7. `IF PTR->NEXT != NULL` - `SET PTR->NEXT->PREV = PTR->PREV` 8. `FREE TEMP` 9. `EXIT` #### Visual Representation ### Circular Linked Lists - **Definition:** A linked list where the last node contains a pointer to the first node, forming a circle. - **Key Feature:** No `NULL` pointer at the end. - **Traversal:** Can traverse the entire list starting from any node and eventually return to the starting node. #### Traversing a Circular Linked List 1. `IF START == NULL` - `Display "List Underflow"` - `EXIT` 2. `SET TEMP = START` 3. `Repeat:` - `Display TEMP->DATA` - `TEMP = TEMP->NEXT` `Until TEMP = START` 4. `STOP` ### Inserting a Node at the Beginning (Circular Linked List) #### Algorithm 1. `NEW_NODE = malloc(sizeof(node))` 2. `SET NEW_NODE->DATA = VAL` 3. `IF START == NULL` - `NEW_NODE->NEXT = NEW_NODE` - `START = NEW_NODE` 4. `ELSE` - `SET PTR = START` - `WHILE PTR->NEXT != START` - `PTR = PTR->NEXT` - `PTR->NEXT = NEW_NODE` - `NEW_NODE->NEXT = START` - `START = NEW_NODE` 5. `EXIT` #### Visual Representation ### Inserting a Node at the End (Circular Linked List) #### Algorithm 1. `NEW_NODE = malloc(sizeof(node))` 2. `SET NEW_NODE->DATA = VAL` 3. `IF START == NULL` - `NEW_NODE->NEXT = NEW_NODE` - `START = NEW_NODE` 4. `ELSE` - `SET PTR = START` - `WHILE PTR->NEXT != START` - `PTR = PTR->NEXT` - `PTR->NEXT = NEW_NODE` - `NEW_NODE->NEXT = START` 5. `EXIT` #### Visual Representation ### Deleting the First Node (Circular Linked List) #### Algorithm 1. `IF START == NULL` - `Write UNDERFLOW` - `EXIT` 2. `SET PTR = START` 3. `IF START->NEXT == START` (Only one node) - `FREE START` - `START = NULL` - `EXIT` 4. `WHILE PTR->NEXT != START` - `PTR = PTR->NEXT` 5. `PTR->NEXT = START->NEXT` 6. `SET TEMP = START` 7. `START = START->NEXT` 8. `FREE TEMP` 9. `EXIT` #### Visual Representation ### Deleting the Last Node (Circular Linked List) #### Algorithm 1. `IF START == NULL` - `Write UNDERFLOW` - `EXIT` 2. `SET PTR = START` 3. `SET PREPTR = START` 4. `IF START->NEXT == START` (Only one node) - `FREE START` - `START = NULL` - `EXIT` 5. `WHILE PTR->NEXT != START` - `PREPTR = PTR` - `PTR = PTR->NEXT` 6. `PREPTR->NEXT = START` 7. `FREE PTR` 8. `EXIT` #### Visual Representation ### Linked Representation of Stacks - **Motivation:** Overcomes the fixed-size limitation of array-based stacks. - **Structure:** Each node in a linked stack has two parts: 1. Data 2. Address of the next node. - **`TOP` Pointer:** The `START` pointer of the linked list is used as the `TOP` of the stack. - **Operations:** All insertions (`Push`) and deletions (`Pop`) are done at the node pointed to by `TOP`. - **Empty Stack:** If `TOP = NULL`, the stack is empty. #### Operations on a Linked Stack - **Push Operation:** Inserts an element at the top. - **Pop Operation:** Deletes the topmost element. - **Peek Operation:** Returns the topmost element without removing it. ### Push Operation (Linked Stack) The push operation adds a new element to the top of the stack. #### Algorithm 1. `NEW_NODE = malloc(sizeof(Node))` 2. `SET NEW_NODE->DATA = VAL` 3. `IF TOP = NULL` - `SET NEW_NODE->NEXT = NULL` - `SET TOP = NEW_NODE` 4. `ELSE` - `SET NEW_NODE->NEXT = TOP` - `TOP = NEW_NODE` 5. `END` #### Visual Representation ### Pop Operation (Linked Stack) The pop operation deletes the topmost element from the stack. #### Algorithm 1. `IF TOP = NULL` - `PRINT UNDERFLOW` - `EXIT` 2. `SET PTR = TOP` 3. `SET TOP = TOP->NEXT` 4. `FREE PTR` 5. `END` #### Visual Representation ### Linked Representation of Queues - **Motivation:** Overcomes the fixed-size limitation of array-based queues. - **Structure:** Each node in a linked queue has two parts: 1. Data 2. Address of the next element. - **Pointers:** - `FRONT`: Points to the first element (head) of the queue. - `REAR`: Points to the last element (tail) of the queue. - **Operations:** - **Insertions (Enqueue):** Done at the `REAR` end. - **Deletions (Dequeue):** Done at the `FRONT` end. - **Empty Queue:** If `FRONT = REAR = NULL`, the queue is empty. #### Operations on Linked Queues - **Enqueue Operation:** Adds an element to the `REAR`. - **Dequeue Operation:** Removes an element from the `FRONT`. - **Peek Operation:** Returns the value of the first element without removing it. ### Enqueue Operation (Linked Queue) #### Algorithm 1. `NEW_NODE = malloc(sizeof(Node))` 2. `SET NEW_NODE->DATA = VAL` 3. `SET NEW_NODE->NEXT = NULL` 4. `IF FRONT = NULL` - `SET FRONT = NEW_NODE` - `SET REAR = NEW_NODE` 5. `ELSE` - `SET REAR->NEXT = NEW_NODE` - `SET REAR = NEW_NODE` 6. `EXIT` #### Visual Representation ### Dequeue Operation (Linked Queue) #### Algorithm 1. `IF FRONT = NULL` - `Write UNDERFLOW` - `EXIT` 2. `SET PTR = FRONT` 3. `SET FRONT = FRONT->NEXT` 4. `IF FRONT = NULL` (If queue becomes empty) - `SET REAR = NULL` 5. `FREE PTR` 6. `END` #### Visual Representation