Linked Lists

A linked list is a data structure for storing objects in a linear order. Each object has data and a pointer to the next objects. Linked lists are similar to arrays with the key difference being the pointer determines the next object not the indices. We generally implement linked lists for a few applications

• Stacks
• Queues
• Hash Tables
• Dynamic Memory Allocation

Linked lists have a pointer to the first node called a head its common to also have a tail pointer.

Here is an example of a singly linked list with pointers flowing in one direction.

Here is an example of a doubly linked list with pointers flowing in both direction.

Here is an example of a circular list where the pointer of the head object points to the tail and tail points to the head.

Common Operations in Linked Lists

Common operations in a linked list usually involve:

• Search
• Insert
• Delete

Operations would need to ensure they respect the head/tail parameters when updating linked lists and utilise the relevant algorithms to ensure efficiency when searching through Prev/Next pointers.