Linked Lists

Data Structures and Algorithms (DSA) in C++: Linked Lists

Linked lists are fundamental data structures in computer science that provide a flexible way to store and organize data. They consist of nodes where each node contains data and a reference (link) to the next node in the sequence. Linked lists allow for efficient insertion and deletion of elements compared to arrays, although they have slower access times due to their linear traversal nature. Here’s a detailed overview of linked lists in C++:

Types of Linked Lists

1. Singly Linked List: Each node contains data and a single link to the next node.
2. Doubly Linked List: Each node contains data and two links: one to the next node and one to the previous node.
3. Circular Linked List: A variation where the last node points back to the first node, forming a circle.

Operations on Linked Lists

1. Traversal: Iterating through the list to access or modify elements.
2. Insertion: Adding a new node at the beginning, end, or middle of the list.
3. Deletion: Removing a node from the list.
4. Search: Finding a node with a specific value.
5. Concatenation: Combining two linked lists into one.

Example: Singly Linked List Implementation in C++

        #include 

          // Node structure for singly linked list
          struct Node {
              int data;
              Node* next;
          
              Node(int val) : data(val), next(nullptr) {}
          };
          
          // Linked list class
          class LinkedList {
          private:
              Node* head;
          
          public:
              LinkedList() : head(nullptr) {}
          
              // Insert new node at the beginning of the list
              void insertAtBeginning(int val) {
                  Node* newNode = new Node(val);
                  newNode->next = head;
                  head = newNode;
              }
          
              // Insert new node at the end of the list
              void insertAtEnd(int val) {
                  Node* newNode = new Node(val);
                  if (head == nullptr) {
                      head = newNode;
                      return;
                  }
          
                  Node* curr = head;
                  while (curr->next != nullptr) {
                      curr = curr->next;
                  }
                  curr->next = newNode;
              }
          
              // Delete node with given value
              void deleteNode(int val) {
                  Node* curr = head;
                  Node* prev = nullptr;
          
                  while (curr != nullptr && curr->data != val) {
                      prev = curr;
                      curr = curr->next;
                  }
          
                  if (curr == nullptr) {
                      std::cout << "Node not found" << std::endl;
                      return;
                  }
          
                  if (prev == nullptr) {
                      head = curr->next;
                  } else {
                      prev->next = curr->next;
                  }
          
                  delete curr;
              }
          
              // Display the linked list
              void display() {
                  Node* curr = head;
                  while (curr != nullptr) {
                      std::cout << curr->data << " ";
                      curr = curr->next;
                  }
                  std::cout << std::endl;
              }
          
              // Destructor to free memory
              ~LinkedList() {
                  Node* curr = head;
                  while (curr != nullptr) {
                      Node* temp = curr;
                      curr = curr->next;
                      delete temp;
                  }
                  head = nullptr;
              }
          };
          
          int main() {
              LinkedList list;
          
              list.insertAtBeginning(10);
              list.insertAtEnd(20);
              list.insertAtEnd(30);
          
              std::cout << "Linked List: ";
              list.display(); // Output: Linked List: 10 20 30
          
              list.deleteNode(20);
          
              std::cout << "Linked List after deletion: ";
              list.display(); // Output: Linked List after deletion: 10 30
          
              return 0;
          }

      

Advantages and Disadvantages of Linked Lists

Advantages:

• Dynamic Size: Easily accommodate varying numbers of elements.
• Efficient Insertions and Deletions: No need for shifting elements, unlike arrays.
• Versatility: Different types (singly, doubly, circular) cater to different needs.

Disadvantages:

• Memory Overhead: Extra memory used for storing pointers.
• No Random Access: Accessing elements requires traversal from the head.
• Complexity: More complex to implement and manage compared to arrays in some scenarios.