Unit 3: Linked lists

A linked list is a linear collection of nodes, where each node contains data and a pointer (link) to the next node. The first node is reached through a pointer called START (or HEAD); the last node's link is NULL.

• Traversal: start with ptr = start; while ptr != NULL, process ptr->data and move ptr = ptr->next.
• Search: traverse and compare each node's data with the item: O(n).

• Insert at end: traverse to the last node and set last->next = newnode, with newnode->next = NULL.
• Insert after a given node: newnode->next = loc->next; loc->next = newnode;
• Delete: make the previous node skip the deleted one: prev->next = loc->next; then free(loc). Deleting the first node changes START.

• Doubly linked list: each node has two pointers, prev and next, so it can be traversed in both directions and a node can be deleted without searching for its predecessor. It uses more memory.
• Circular linked list: the last node points back to the first instead of NULL, so the list can be traversed from any node. It is useful for round-robin scheduling.

• Dynamic allocation: memory requested at run time — malloc, calloc, realloc and free in C; new and delete in C++.
• Free list (available space list): a linked list of free memory blocks maintained by the system.
• Allocation strategies: first fit, best fit, worst fit; fragmentation — external (scattered free blocks) and internal (unused space inside blocks); compaction merges free blocks.

cstruct node *p = (struct node *) malloc(sizeof(struct node));
if (p == NULL) { printf("Overflow\n"); }
free(p);   /* return memory to the free pool */

• Generalised list: a list whose elements may be atoms or lists themselves — e.g., (a, (b, c), d).
• Node structure: a tag field (atom or list), a data or down-pointer field and a next pointer.
• Uses: representing polynomials in several variables, LISP data, nested structures.

• Garbage: memory blocks no longer reachable from any pointer.
• Garbage collection: automatically finding and reclaiming such memory.

• Other methods: reference counting (fails with cycles), copying collectors; languages such as Java and Python collect garbage automatically, while C requires manual free.
• Memory leak: allocated memory never freed and no longer reachable.