Linked lists

Unlike a contiguous block of memory, order in linked lists is determined by a pointer in each object.

The head of a linked list is the first node, and it's tail is the last node.

Searching a linked list is $O(n)$ in the worst-case.

Inserting a node before the current head, or at any specific place if you have a pointer to that specific place, is $O(1)$ .

Deleteing a node takes $O(1)$ time if you have a pointer to that node (otherwise search is $O(n)$ ). Also, deletion is $O(1)$ in a doubly linked list, whereas it's $O(n)$ in the worst case for a singly linked list.

Insertion and deletion are faster for linked lists than for arrays, but finding the $k$ ^th element in an array would be $O(n)$ time in an array whereas it would be $O(k)$ time in a linked list.

A sentinel is a dummy object that simplified boundary conditions. The sentinel represents NIL but has the attributes of a node (next, key, prev if doubly linked). Using sentinels doesn't change the asymptotic run time of linked list operations, but can decrease the constant factor.

struct Node {
  int value;
  struct Node* prev;
  struct Node* next;
}

// Search head for v
struct Node* list_search(struct Node* head, int v) {
  struct Node* i = head;
  while (i && i->key != v)
    i = i.next;
  return i;
}

// Prepend x to the head
void list_prepend(struct Node* head, struct Node* x) {
  x->next = head;
  x->prev = NULL;
  if (head)
    head->prev = x;
  head = x;
}

// Insert x after y
  void list_insert(struct Node* x, struct Node* y) {
  x->next = y->next;
  x->prev = y;
  if (y->next)
    y->next->prev = x;
  y->next = x;
}

void list_delete(struct Node* head, struct Node* x) {
  if (x->prev)
    x->prev->next = x->next;
  else
    head = x->next;
  if (x->next)
    x->next->prev = x->prev;
}