Linked list

February 17, 2016

Linked list is one of the most common data structure. It's a linear collection of data element. This data structure is composed of a sequence of nodes. Every node has data and a reference (a pointer in C++) to the next node which is NULL if it's the last. To keep track of the list, we usually get a pointer to the first element.

figure 0
Linked list

The principal reason to use linked list over array is its dynamic structure. We have the possibility to add a new node whenever we want. Insertion and deletion are relatively easy operations. We can consider some tweaks in order to compensate for some weaknesses. For instance, one can add a pointer to the last element to avoid traversing all nodes for the last one. The first element is called head and the rest of the list is the tail.

Moreover, several alternatives exist for linked lists, here are two:

  • Doubly linked list
  • Circular linked list

While lists are a well fit for maintaining a changing set, they also have disadvantages.

  • They have a sequencial access, accessing the ith element of the list takes O(i)

  • Nodes are stored incontiguously on disk which has the result to increase the time for access individual element

  • They need more memory to store the pointers

    one way

  • Reverse traversing is cumbersome as the pointers go only one way, the doubly linked list resolves this problem.

C++ implementation

struct Node {
  int data;
  Node * next;
  Node(int n) : data(n) { }
};

class linkedList {
public:
  linkedList() {
    first = NULL;
  };
  void pushBack(int el);
  bool deleteNode(int el);
private:
  Node * first;
};

Push back

The push back method inserts a new node at the end of the list.

void pushBack(int el) {
  Node * newNode = new Node(el);
  if (first == NULL) {
    first = newNode;
    return;
  }
  Node * p = first;
  while (p->next != NULL) {
    p = p->next;
  }
  p->next = newNode;
}

Delete node

Delete node method removes the first node of a specific value and returns true or false whether a corresponding node was found.

bool deleteNode(int el) {
  Node *curr = first;
  if (curr == NULL) { return false; }
  if (curr->data == el) {
    first = curr->next;
    delete curr;
    return true;
  }
  if (curr->next == NULL) {
    return false;
  }
  curr = curr->next;
  Node *prev = first;
  while (curr != NULL) {
    if (curr->data == el) {
      prev->next = curr->next;
      delete curr;
      return true;
    }
    prev = curr;
    curr = curr->next;
  }
  return false;
}

References:

  1. Linked list - wikipedia
  2. Doubly linked list - wikipedia
  3. Singly linked list - cprogramming
  4. Linked List Problems - cslibrary.stanford.edu