A linked list is a linear data structure where elements, called nodes, are stored in a sequence. Unlike arrays, the elements in a linked list are not stored in contiguous memory locations. Each node contains two parts:
- Data: The value or information stored in the node.
- Pointer (or Reference): A reference to the next node in the sequence.
- Accessing an element in a singly linked list requires traversing the list, resulting in an average time complexity of O(n), where n is the number of elements in the list.
- Inserting an element at a specific position in the list requires traversing to that position and updating the pointers of adjacent nodes, resulting in a worst-case time complexity of O(n), where n is the number of elements in the list.
- Deleting an element at a specific position in the list requires traversing to that position and updating the pointers of adjacent nodes, resulting in a worst-case time complexity of O(n), where n is the number of elements in the list.
Note: Accessing or updating the first element of a singly linked list can be done in constant time, O(1), since the head of the list is always known.
- Each node points to the next node in the sequence.
- The last node points to null (or None in Python), indicating the end of the list.
- Each node contains two references: one to the next node and one to the previous node.
- This allows traversal in both directions (forward and backward).
- The last node points back to the first node instead of null, creating a loop.
- This can be implemented in both singly and doubly linked lists.
