Linked Lists

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.

linked-list.png

Nodes in doubly linked lists also contain a reference to the predecessor.

doubly-linked-list.png

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.

Implementation

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

Search

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

Reverse

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

Find Cycle

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