​
Advanced Lists

​
1. Memory-Efficient Doubly Linked List

class MENode:
    def __init__(self, val=0):
        self.val = val
        self.npx = 0  # XOR of next and prev addresses
        
class MemoryEfficientDLL:
    def __init__(self):
        self.head = None
        self.nodes = []  # Keep references to prevent garbage collection
    
    def _get_addr(self, node):
        """Get memory address of node"""
        return id(node) if node else 0
    
    def _xor(self, a, b):
        """XOR of two node addresses"""
        return a ^ b
    
    def insert_beginning(self, val):
        new_node = MENode(val)
        if not self.head:
            self.head = new_node
        else:
            new_node.npx = self._get_addr(self.head)
            self.head.npx = self._xor(self._get_addr(new_node), 
                                    self.head.npx)
            self.head = new_node
        self.nodes.append(new_node)
    
    def traverse(self):
        if not self.head:
            return []
        
        result = []
        curr = self.head
        prev_addr = 0
        
        while curr:
            result.append(curr.val)
            next_addr = self._xor(prev_addr, curr.npx)
            if not next_addr:
                break
            # Find next node
            prev_addr = self._get_addr(curr)
            curr = self._find_node(next_addr)
        
        return result
    
    def _find_node(self, addr):
        """Find node by memory address"""
        for node in self.nodes:
            if self._get_addr(node) == addr:
                return node
        return None

​
2. XOR Linked List

class XORNode:
    def __init__(self, val=0):
        self.val = val
        self.npx = None  # XOR of next and prev pointers

class XORLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.nodes = []  # Keep references
    
    def insert(self, val):
        new_node = XORNode(val)
        self.nodes.append(new_node)
        
        if not self.head:
            self.head = new_node
            self.tail = new_node
            return
        
        # Update tail's npx
        self.tail.npx = self._xor(self._get_ptr(self.tail.npx), 
                                 self._get_ptr(new_node))
        # Set new node's npx
        new_node.npx = self._get_ptr(self.tail)
        self.tail = new_node
    
    def _xor(self, a, b):
        return 0 if a is None and b is None else (
            a if b is None else (
            b if a is None else 
            a ^ b))
    
    def _get_ptr(self, node):
        return id(node) if node else 0
    
    def traverse_forward(self):
        if not self.head:
            return []
        
        result = []
        curr = self.head
        prev_ptr = 0
        
        while curr:
            result.append(curr.val)
            next_ptr = self._xor(prev_ptr, curr.npx)
            if not next_ptr:
                break
            prev_ptr = self._get_ptr(curr)
            curr = self._find_node(next_ptr)
            
        return result

​
3. Skip List (Optimized)

import random

class SkipNode:
    __slots__ = ['val', 'next', 'width']  # Memory optimization
    
    def __init__(self, val, level):
        self.val = val
        self.next = [None] * level
        self.width = [1] * level  # Distance to next node at each level

class OptimizedSkipList:
    def __init__(self, max_level=16):
        self.max_level = max_level
        self.head = SkipNode(float('-inf'), max_level)
        self.level = 0
        self.size = 0
    
    def _random_level(self):
        level = 0
        while random.random() < 0.5 and level < self.max_level - 1:
            level += 1
        return level
    
    def insert(self, val):
        update = [None] * self.max_level
        width_update = [0] * self.max_level
        current = self.head
        
        # Calculate width updates
        for i in range(self.level, -1, -1):
            while (current.next[i] and 
                   current.next[i].val < val):
                width_update[i] += current.width[i]
                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
                width_update[i] = self.size
            self.level = level
        
        new_node = SkipNode(val, level + 1)
        for i in range(level + 1):
            new_node.next[i] = update[i].next[i]
            update[i].next[i] = new_node
            # Update widths
            new_node.width[i] = (width_update[i] + 1 if update[i] == self.head
                               else update[i].width[i] - width_update[i])
            update[i].width[i] = width_update[i] + 1
        
        self.size += 1
    
    def search(self, val):
        current = self.head
        
        for i in range(self.level, -1, -1):
            while current.next[i] and current.next[i].val < val:
                current = current.next[i]
        
        current = current.next[0]
        return current and current.val == val

​
4. Self-Organizing List

class SelfOrgNode:
    __slots__ = ['val', 'next', 'access_count']
    
    def __init__(self, val):
        self.val = val
        self.next = None
        self.access_count = 0

class SelfOrganizingList:
    def __init__(self, strategy='move_to_front'):
        self.head = None
        self.strategy = strategy
    
    def insert(self, val):
        new_node = SelfOrgNode(val)
        new_node.next = self.head
        self.head = new_node
    
    def find(self, val):
        if not self.head:
            return None
        
        prev = None
        curr = self.head
        
        while curr and curr.val != val:
            prev = curr
            curr = curr.next
        
        if not curr:
            return None
        
        curr.access_count += 1
        
        if self.strategy == 'move_to_front' and prev:
            prev.next = curr.next
            curr.next = self.head
            self.head = curr
        elif self.strategy == 'transpose' and prev:
            if prev != self.head:
                # Find previous to prev
                temp = self.head
                while temp.next != prev:
                    temp = temp.next
                # Swap nodes
                temp.next = curr
                prev.next = curr.next
                curr.next = prev
        
        return curr.val

​
5. Unrolled Linked List

class UnrolledNode:
    def __init__(self, max_elements=16):
        self.elements = []
        self.max_elements = max_elements
        self.next = None

class UnrolledLinkedList:
    def __init__(self, node_capacity=16):
        self.head = None
        self.node_capacity = node_capacity
        self.size = 0
    
    def insert(self, val, index):
        if index < 0 or index > self.size:
            raise IndexError("Index out of range")
        
        if not self.head:
            self.head = UnrolledNode(self.node_capacity)
            self.head.elements.append(val)
            self.size += 1
            return
        
        # Find the node and position
        current = self.head
        pos = index
        
        while pos > len(current.elements):
            pos -= len(current.elements)
            current = current.next
            if not current:
                current = UnrolledNode(self.node_capacity)
                break
        
        current.elements.insert(pos, val)
        self.size += 1
        
        # Rebalance if necessary
        self._rebalance(current)
    
    def _rebalance(self, node):
        while node and len(node.elements) > node.max_elements:
            # Split node
            mid = len(node.elements) // 2
            new_node = UnrolledNode(self.node_capacity)
            new_node.elements = node.elements[mid:]
            new_node.next = node.next
            node.elements = node.elements[:mid]
            node.next = new_node
            node = new_node
    
    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of range")
        
        current = self.head
        pos = index
        
        while pos >= len(current.elements):
            pos -= len(current.elements)
            current = current.next
        
        return current.elements[pos]

​
Time Complexities

OperationMEF DLLXOR ListSkip ListSelf-Org ListUnrolled List
Insert FrontO(1)O(1)O(log n)O(1)O(√n)
Insert MiddleO(n)O(n)O(log n)O(n)O(√n)
DeleteO(n)O(n)O(log n)O(n)O(√n)
SearchO(n)O(n)O(log n)O(n)*O(√n)
Space/NodeO(1)O(1)O(log n)O(1)O(√n)

* Improves with self-organizing strategies

​
Space Complexities

ImplementationSpace/NodeAdditional SpaceTotal Space
MEF DLLO(1)O(n)O(n)
XOR ListO(1)O(n)O(n)
Skip ListO(log n)O(1)O(n log n)
Self-Org ListO(1)O(1)O(n)
Unrolled ListO(√n)O(1)O(n)

​
Memory Optimization Techniques

  1. Node Memory Management
class NodePool:
    def __init__(self, size=1000):
        self.pool = []
        self.available = []
        self.size = size
    
    def get_node(self, node_type, *args):
        if not self.available:
            if len(self.pool) < self.size:
                node = node_type(*args)
                self.pool.append(node)
                return node
        else:
            return self.available.pop()
        return None
    
    def return_node(self, node):
        if len(self.available) < self.size:
            self.available.append(node)
  1. Efficient Memory Layout
from array import array

class CompactList:
    def __init__(self, chunk_size=16):
        self.data = array('i')  # integer array
        self.chunk_size = chunk_size
        self.chunks = []
    
    def add_chunk(self):
        new_chunk = array('i', [0] * self.chunk_size)
        self.chunks.append(new_chunk)

​
Edge Cases to Consider

  1. Empty List Operations
def handle_empty_list(self):
    if not self.head:
        raise ValueError("Operation on empty list")
  1. Single Node Operations
def handle_single_node(self):
    if self.head and not self.head.next:
        # Special handling for single node
        pass
  1. Boundary Conditions
def handle_boundaries(self, index):
    if index < 0 or index >= self.size:
        raise IndexError("Index out of range")

​
Performance Considerations

  1. Cache Optimization
def optimize_node_layout(self):
    # Arrange nodes to maximize cache hits
    current = self.head
    cache_line = []
    
    while current:
        if len(cache_line) == 64: # Cache line size
            self._rearrange_nodes(cache_line)
            cache_line = []
        cache_line.append(current)
        current = current.next
  1. Batch Operations
def batch_insert(self, values, batch_size=1000):
    buffer = []
    for val in values:
        buffer.append(val)
        if len(buffer) == batch_size:
            self._process_batch(buffer)
            buffer = []
    if buffer:
        self._process_batch(buffer)

​
Common Pitfalls

  1. Memory Leaks
# Wrong
def delete_wrong(self, node):
    node.next = node.next.next  # Memory leak

# Correct
def delete_correct(self, node):
    temp = node.next
    node.next = temp.next
    temp.next = None  # Clean reference
  1. Reference Handling
# Wrong
def update_wrong(self):
    self.head = self.head.next  # Lost reference

# Correct
def update_correct(self):
    old_head = self.head
    self.head = old_head.next
    old_head.next = None
  1. XOR Operation Safety
# Wrong
def xor_wrong(self, a, b):
    return a ^ b  # May cause errors with None

# Correct
def xor_correct(self, a, b):
    return 0 if not (a or b) else (
        a if not b else (
        b if not a else a ^ b))
MatrixSplay tree