A linked list is a linear data structure, much like an array, but it stores elements non-contiguously in memory. Instead of contiguous blocks, a linked list consists of a sequence of nodes, where each node contains both data and a reference to the next node in the sequence. The first node is called the head, and the last node's pointer typically points to null or None, signifying the end of the list.
Unlike arrays, linked lists are dynamic in size and excel at insertions and deletions because elements do not need to be shifted. However, accessing an element by its index is less efficient, as it requires traversing the list from the beginning.
Linked list traversal involves visiting each node in the list exactly once, starting from the head and following the next pointers until the end of the list, which is a null pointer, is reached. This operation is fundamental for searching, printing all elements, or performing an action on each node. Though both arrays and linked lists take O(n) time for traversal, linked lists are generally slower with this operation. This is due to the fact that arrays are contiguously located in memory, hence the CPU can prefetch the subsequent elements making traversal slightly faster. Linked lists also require pointer dereferencing since they are scattered throughout and connected by pointers only.
Insertion adds a new node to the linked list. This can typically occur at three positions:
Deletion removes a node from the linked list. Similar to insertion, deletion can occur at various positions: