В чем разница между List и LinkedList?

Разница между List и LinkedList в Python

Вопрос немного трёхий, потому что в стандартной библиотеке Python есть list (встроенный тип), а LinkedList — это данная структура, которую обычно реализуют вручную или используют из collections.deque.

Python list — это не связный список

list в Python — это динамический массив, а не связный список:

# list — работает как динамический массив
my_list = [1, 2, 3]
my_list.append(4)  # O(1) amortized
my_list[0]         # O(1) — прямой доступ по индексу

Характеристики list:

• Структура: динамический массив (содержит указатели на объекты)
• Доступ по индексу: O(1) — очень быстро
• Добавление в конец: O(1) amortized
• Добавление в начало: O(n) — нужно сдвинуть все элементы
• Удаление из начала: O(n)
• Память: более компактная при полном заполнении

LinkedList — связный список

LinkedList — это структура данных из отдельных узлов, связанных указателями:

# Вручную реализованный связный список
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):  # O(n) — нужно дойти до конца
        node = Node(data)
        if not self.head:
            self.head = node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = node
    
    def insert_at_start(self, data):  # O(1) — просто создаём новый узел
        node = Node(data)
        node.next = self.head
        self.head = node
    
    def access_by_index(self, index):  # O(n) — нужно пройти от начала
        current = self.head
        for _ in range(index):
            if not current:
                return None
            current = current.next
        return current.data if current else None

Характеристики LinkedList:

• Структура: узлы с указателями друг на друга
• Доступ по индексу: O(n) — нужно пройти от начала
• Добавление в начало: O(1)
• Добавление в конец: O(n) (без хвоста) или O(1) (с хвостом)
• Удаление из начала: O(1)
• Память: больше расходует на указатели в каждом узле

Сравнительная таблица

Когда что использовать

Используй list когда:

• Нужен быстрый доступ по индексу
• Много операций чтения
• Стандартный набор операций с коллекцией

Используй LinkedList когда:

• Часто добавляешь/удаляешь элементы в начало
• Размер очень большой и часто меняется
• Нужна экономия памяти в определённых сценариях

Python collections.deque — лучшее из обоих

Для работы с очередями и двусторонними операциями используй deque:

from collections import deque

d = deque([1, 2, 3])
d.appendleft(0)  # O(1) — добавление в начало
d.append(4)      # O(1) — добавление в конец
d.popleft()      # O(1) — удаление из начала
d.pop()          # O(1) — удаление из конца

В практике: 99% случаев используй list, 1% — deque для специфических задач.