Linked list

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return
        
        current = self.head
        while current.next:
            current = current.next
        current.next = Node(data)
    
    def delete(self, data):
        if not self.head:
            return
        
        if self.head.data == data:
            self.head = self.head.next
            return
        
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

class DNode:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def append(self, data):
        new_node = DNode(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            return
        
        new_node.prev = self.tail
        self.tail.next = new_node
        self.tail = new_node
    
    def delete(self, data):
        current = self.head
        while current:
            if current.data == data:
                if current.prev:
                    current.prev.next = current.next
                else:
                    self.head = current.next
                
                if current.next:
                    current.next.prev = current.prev
                else:
                    self.tail = current.prev
                return
            current = current.next

class CircularLinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
            return
        
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head

import random

class SkipNode:
    def __init__(self, data, level):
        self.data = data
        self.next = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level):
        self.max_level = max_level
        self.head = SkipNode(None, max_level)
        self.level = 0
    
    def random_level(self):
        level = 0
        while random.random() < 0.5 and level < self.max_level:
            level += 1
        return level
    
    def insert(self, data):
        update = [None] * (self.max_level + 1)
        current = self.head
        
        for i in range(self.level, -1, -1):
            while current.next[i] and current.next[i].data < data:
                current = current.next[i]
            update[i] = current
        
        level = self.random_level()
        if level > self.level:
            for i in range(self.level + 1, level + 1):
                update[i] = self.head
            self.level = level
        
        new_node = SkipNode(data, level)
        for i in range(level + 1):
            new_node.next[i] = update[i].next[i]
            update[i].next[i] = new_node

if not self.head:
    return None

if not self.head.next:
    # Handle single node case
    return self.head.data

if current.next is None:
    # Handle last node
    self.tail = current.prev

def has_cycle(self):
    if not self.head:
        return False
    
    slow = fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

class OptimizedList:
    def __init__(self):
        self.head = None
        self.tail = None  # Maintain tail pointer
    
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            return
        
        self.tail.next = new_node
        self.tail = new_node  # O(1) append

class TrackedList:
    def __init__(self):
        self.head = None
        self.length = 0  # Track length
    
    def append(self, data):
        # ... append logic ...
        self.length += 1

def batch_insert(self, data_list):
    current = self.head
    while current.next:
        current = current.next
    
    # Build nodes in memory first
    for data in data_list:
        current.next = Node(data)
        current = current.next

def delete_node(self, node):
    if node.next:
        node.data = node.next.data
        node.next = node.next.next
    node.next = None  # Clear reference

def clear_list(self):
    current = self.head
    while current:
        next_node = current.next
        current.next = None  # Break references
        current.data = None
        current = next_node
    self.head = None

class NodePool:
    def __init__(self, size):
        self.pool = [Node(None) for _ in range(size)]
        self.available = list(range(size))
    
    def get_node(self):
        if self.available:
            return self.pool[self.available.pop()]
        return Node(None)  # Fallback

def traverse_batch(self, batch_size=1000):
    current = self.head
    batch = []
    
    while current:
        batch.append(current.data)
        if len(batch) == batch_size:
            process_batch(batch)
            batch = []
        current = current.next

class LinkedList:
    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

# Wrong
self.head = self.head.next
self.head.prev = None  # Error if head is None

# Correct
if self.head:
    self.head = self.head.next
    if self.head:
        self.head.prev = None

# Memory leak
def delete_circular(self, node):
    if node.next == node:  # Single node
        self.head = None
        return
    
    # Wrong: circular reference remains
    node.next = node.next.next
    
    # Correct: break circular reference
    current = self.head
    while current.next != node:
        current = current.next
    current.next = node.next

# Poor distribution
def bad_random_level(self):
    return random.randint(0, self.max_level)

# Better distribution
def good_random_level(self):
    level = 0
    while random.random() < 0.5 and level < self.max_level:
        level += 1
    return level