linked list.docx

1. Introduction to Linked List ============================== A linked list is a linear data structure where elements (nodes) are stored in sequence, but not in contiguous memory locations. Each node contains two parts:\ 1. Data: The value stored in the node.\ 2. Pointer: A reference to the next no...

1. Introduction to Linked List ============================== A linked list is a linear data structure where elements (nodes) are stored in sequence, but not in contiguous memory locations. Each node contains two parts:\ 1. Data: The value stored in the node.\ 2. Pointer: A reference to the next node in the sequence. Example Structure in C:\ struct Node {\ int data;\ struct Node\* next;\ }; 2. Types of Linked Lists ======================== Singly Linked List: ------------------- Each node points to the next node and the last node points to NULL.\ \ struct Node {\ int data;\ struct Node\* next;\ }; Doubly Linked List: ------------------- Each node contains two pointers, one pointing to the next node and one pointing to the previous node.\ \ struct Node {\ int data;\ struct Node\* next;\ struct Node\* prev;\ }; Circular Linked List: --------------------- The last node points to the first node instead of NULL.\ \ struct Node {\ int data;\ struct Node\* next;\ }; 3. Basic Operations on Linked Lists =================================== Insertion: ---------- Insertion can be done at the beginning, end, or a specific position in the list. ### At the Beginning: void insertAtBeginning(struct Node\*\* head, int newData) {\ struct Node\* newNode = (struct Node\*)malloc(sizeof(struct Node));\ newNode-\>data = newData;\ newNode-\>next = \*head;\ \*head = newNode;\ } ### At the End: void insertAtEnd(struct Node\*\* head, int newData) {\ struct Node\* newNode = (struct Node\*)malloc(sizeof(struct Node));\ struct Node\* temp = \*head;\ newNode-\>data = newData;\ newNode-\>next = NULL;\ if (\*head == NULL) {\ \*head = newNode;\ return;\ }\ while (temp-\>next != NULL) {\ temp = temp-\>next;\ }\ temp-\>next = newNode;\ } Deletion: --------- Deletion can be performed at the beginning, end, or a specific position. ### At the Beginning: void deleteAtBeginning(struct Node\*\* head) {\ if (\*head == NULL) return;\ struct Node\* temp = \*head;\ \*head = (\*head)-\>next;\ free(temp);\ } ### At the End: void deleteAtEnd(struct Node\*\* head) {\ if (\*head == NULL) return;\ struct Node\* temp = \*head;\ struct Node\* prev = NULL;\ while (temp-\>next != NULL) {\ prev = temp;\ temp = temp-\>next;\ }\ if (prev != NULL)\ prev-\>next = NULL;\ else\ \*head = NULL;\ free(temp);\ } Traversal: ---------- void traverse(struct Node\* head) {\ struct Node\* temp = head;\ while (temp != NULL) {\ printf(\"%d -\> \", temp-\>data);\ temp = temp-\>next;\ }\ printf(\"NULL\\n\");\ } 4. Advantages of Linked List ============================ 1\. Dynamic Size: Unlike arrays, linked lists can grow or shrink in size dynamically during runtime.\ 2. Efficient Insertion/Deletion: Easy to insert or delete elements without shifting other elements, unlike arrays. 5. Disadvantages of Linked List =============================== 1\. Memory Overhead: Each node requires extra memory for storing the pointer.\ 2. Sequential Access: Linked lists do not provide direct access to elements like arrays (no indexing). 6. Applications of Linked Lists =============================== 1\. Implementing Stacks and Queues.\ 2. Graph Adjacency Representation.\ 3. Dynamic Memory Allocation.\ 4. Polynomial Arithmetic.