Created: 2023-08-21 13:12
Status: #concept
Subject: Programming
Tags: C Dynamic Memory Data Structure JavaScript Array struct Cursor Implementation

Linked List

A linear chain of structs of Node types that contain;

  • the data held by the node
  • a Pointer to the next Node or NULL, representing the end of the list.
  • the first node is called the "head" while the last node pointing to NULL is the "tail".

Linked List Representation.png

Example

First we create the head node:

struct node {
  int data; // data stored in node
  struct node *link; // pointer to the next node
};

// setting *first to NULL indicates the list is empty
struct node *first = NULL;

To create more nodes, we need to use malloc(sizeof (struct node)).

struct node *new_node; // buffer pointer for a new node until we insert to list

new_node = (struct node *) malloc(sizeof(struct node)); // allocates memory

Benefits Over Arrays

They don't need to be contiguously stored and they are more flexible in terms of memory consumption.

C arrays are statically-sized, so they always allocate a specific amount of Bytes, unless we manually realloc() the memory and copy values.

Linked Lists only allocate enough memory for a single node, however each element takes more space than a single normal array element because it needs to save the pointer to the next element.

Deleting nodes in a Linked List is also very easy because we can just let a node point to NULL and it will cut all links to the other nodes, however we still need to consider free()'ing them to prevent Memory Leaks.

Drawbacks

Traversing a linked list involves accessing each node starting from the head until you reach the tail.

  • O(n) is the time complexity to access linked list nodes.
  • O(1) is the time complexity for accessing C Array elements.

Normal C arrays are contiguously stored in memory and we can calculate the address of any element easily as long as we have the first element's pointer and size since each element is separated by a static number of Bytes.

Linked Lists, on the other hand, can have nodes pointing to other nodes in random places in our RAM Memory due to Dynamic Memory Allocation from the Memory Heap, therefore we will need to traverse from the first node unless we Cache a specific node to start searching from or use another data structure like a Circular Linked List.

Operations

Assuming the types are as follows;

typedef struct node {
  char data;
  struct node *link;
} Node, *List;

Traversal

void printLinkedList(List *head) {
  for (List trav = *head; trav != NULL; trav = cur->link) {
    printf("%zu(%c)->", cur, cur->data);
  }
  puts("NULL");
}

Alternatively, we can use List *trav, a double Pointer to traverse:

void displayList(List *L) {
  List *trav;
  for (trav = L; *trav != NULL; trav = &(*trav)->link) {
    printf("(%c)->", (*trav)->data);
  }
  puts("NULL");
}

Insertion

void insertFirst(List *A, char elem) {
  Node *newNode = malloc(sizeof(Node));
  
  if (newNode != NULL) {
    newNode->data = elem;
    newNode->link = *A;
    *A = newNode;
  }
}

Deletion

The Algorithm is as follows:

  1. Locate the node to be deleted.
  2. Alter the previous node so that it “bypasses” the deleted node and points to the next node after it.
  3. Call free() to reclaim the space occupied by the deleted node.
void deleteElem(List *A, char elem) {
  List *trav;
  for (trav = A; *trav != NULL && (*trav)->data != elem; trav = &(*trav)->link) 
    {}

  if (*trav != NULL) {
    List tmp = *trav;
    *trav = (*trav)->link;
    free(tmp);
  }
}

References