DILI #9: Linked Lists

Linked lists, a powerful data structure that can be used for a variety of tasks. They are a better choice than arrays for storing data that is not known in advance, and are also efficient for performing operations such as insertion and deletion. For reference, this is a perfect illustration of an array and a linked list.

To describe what is happening, a linked list is a linear data structure in which each element, called a node, contains data and a pointer to the next node in the list. The first node in the list is called the head, and the last node is called the tail.

Linked lists are a dynamic data structure(remember Vectors?), which means that they can grow and shrink as needed. This makes them ideal for storing data that is not known in advance, such as the results of a search query.

There are primarily 2 types: singly and doubly linked lists. Singly can only access the next node as such:

And doubly linked lists can access both the previous and the next nodes as such:

With that, here's an example of a linked list:

struct Node {
  int data;
  Node* next;
};

Node* head = nullptr;
Node* tail = nullptr;

void insert(int data) {
  Node* newNode = new Node();
  newNode->data = data;
  newNode->next = nullptr;

  if (head == nullptr) {
    head = newNode;
    tail = newNode;
  } else {
    tail->next = newNode;
    tail = newNode;
  }
}

void printList() {
  Node* current = head;
  while (current != nullptr) {
    cout << current->data << " ";
    current = current->next;
  }
}

int main() {
  insert(10);
  insert(20);
  insert(30);

  printList();

  return 0;
}

This code creates a linked list with three nodes, and then prints the list to the console.

Anyways, there are a variety of other things you can do as well:

• Inserting a node
• Deleting a node
• Searching for a node
• Traversing the list
• Reversing the list
• Sorting the list These operations can be implemented using pointers and can be done recursively or iteratively.

For example, given the set up above, this is a program which would insert a new node at a given ith index:

 void addAtIndex(int index, int val) {
        // Return if invalid index
        if (index>size || index < 0) {
            return;
        }
        Node* current= head;
        Node* new_node = new Node(val);
        // index == 0 implies insert at head
        // Considered separately as we need to update head
        if (index == 0) {
            new_node->next = current;
            // Update head
            head = new_node;
        }
        else {
            // Run loop till index-1 as we need to insert node at index
            for(int i=0;i<index-1;++i) {
                current= current->next;
            }
            /* 
                current --> current->next
                            /
                        new_node

                current    current->next
                      \      /
                        new_node           

            */            
            new_node->next = current->next;
            current->next = new_node;
        }
        // Increase size whenever we insert node
        size++;
    }

Similarly, you can do the deletion as well.

Learning linked lists in C++ is like learning how to ride a unicycle. It's a pain in the *ss at first, but once you get the hang of it, you'll be glad you did.

Just kidding, linked lists are actually pretty cool. They're a powerful data structure that can be used for a variety of tasks. If you're interested in learning more about linked lists, I encourage you to check out the resources that I have listed down below in the references.

And who knows, maybe you'll even learn how to ride a unicycle along the way.

REFERENCES:
GeeksforGeeks
LeetCode
William Fiset on YT