A linked list is a data structure that stores items in sequence. Each node contains a value and a reference to the next node in the list. The first node is the head and the last node is the tail. The tail's next field is null.
Nodes in doubly linked lists also contain a reference to the predecessor.
Linked Lists vs. Arrays
A list is similar to an array in that it contains objects in linear order. The key differences are that inserting and deleting elements in a list has time complexity \(O(1)\). On the other hand, obtaining the kth element in a list is expensive, having \(O(n)\) time complexity.
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def search(key, linked_list): """Find the Node with value=key. Return None if not found.""" while linked_list and linked_list.key != key: linked_list = linked_list.next return linked_list
def reverse(head): """Reverse a singly linked list.""" to_return = None while head: buffer = head head = head.next buffer.next = to_return to_return = buffer return to_return
def has_cycle(head): """Use Floyd's Tortoise and Hare algorithm to check for a cycle.""" slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if fast is slow: return True return False