Linked Lists

Linked Lists are a fundamental data structureThe organisation and order of information in a text. in computer science. They are a way to storeThe stage where the CPU saves the result of the execution back into memory or registers. a collection of elements, called nodes, in a linear order. Each node in a linked list contains a value and a reference to the next node in the list. The first node in the list is called the head, and the last node is called the tail.

One of the key characteristics of linked lists is that the elements are not stored in contiguous memoryA unified system that stores both data and program instructions in the same location. locations, unlike arrays. Instead, each element is stored in its own memory location, and the references to the next element are stored with each element. This allows for efficient insertion and deletion of elements, as elements do not need to be shifted around in memory.

There are two types of linked lists: singly linked lists and doubly linked lists. In a singly linked list, each node has a reference to the next node, but not the previous one. In a doubly linked list, each node has a reference to both the next and the previous node.

To insert an element into a linked list, you can add it to the head of the list, the tail of the list, or a specific position in the list. To add an element to the head of the list, you simply create a new node with the value you want to insert and set it as the new head of the list, with the current head as its next element. To add an element to the tail of the list, you create a new node with the value you want to insert, and set the current tail's next reference to the new node. To add an element to a specific position, you traverse the list to find the desired position, and set the new node's next reference to the current node's next reference.

Deleting an element from a linked list is similar to inserting an element. To delete the head of the list, you simply set the head to the next node. To delete the tail of the list, you traverse the list to find the second to last node and set its next reference to null. To delete an element from a specific position, you traverse the list to find the node before the one you want to delete, and set its next reference to the current node's next reference.

Traversing a linked list means visiting every element in the list. To traverse a singly linked list, you start at the head of the list and follow the next references until you reach the end of the list. To traverse a doubly linked list, you can start at the head of the list and follow the next references, or you can start at the tail of the list and follow the previous references.