Связные списки: введение

Как и массивы, связные списки являются линейной структурой данных. Но в отличие от массивов, элементы связного списка не хранятся в смежном расположении; они связаны с помощью указателей.



Почему LinkedList?

Массивы могут использоваться для хранения линейных данных аналогичных типов, но имеют следующие ограничения.

1. размер массивов фиксирован: поэтому мы должны заранее знать верхний предел количества элементов. Также, как правило, выделяемая память равна верхнему пределу независимо от использования.
2. вставка нового элемента в массив элементов является затратной операцией, так как для новых элементов необходимо создать место, а для создания места необходимо переместить существующие элементы.

Например, в системе, если мы поддерживаем сортированный список идентификаторов в array id[].

id[] = [1000, 1010, 1050, 2000, 2040].

И если мы хотим вставить новый ID 1005, то для поддержания отсортированного порядка, мы должны переместить все элементы после 1000 (исключая 1000).

Удаление также дорого обходится в массивах до тех пор, пока не будут использованы некоторые специальные методы. Например, чтобы удалить 1010 в id [], все после 1010 должно быть перемещено.

Преимущества над массивами

1. динамический размер
2. легкость вставки / удаления

Недостатки:

1. случайный доступ не допускается. Мы должны получить доступ к элементам последовательно, начиная с первого узла. Таким образом, мы не можем эффективно выполнять двоичный поиск со связанными списками с его реализацией по умолчанию.
2. с каждым элементом списка требуется дополнительное место для указателя.
3. нет кэширования. Поскольку элементы массива являются смежными местоположениями, существует локальность ссылки, которой нет в случае связанных списков.

Связанный список представлен указателем на первый узел связанного списка. Первый узел называется head. Если связанный список пуст, то значение head равно NULL. Каждый узел в списке состоит по крайней мере из двух частей:

1. Данные
2. указатель (или ссылка) на следующий узел

В C мы можем представить узел, используя структуры. В Java или C# LinkedList может быть представлен как класс, а узел как отдельный класс. Класс LinkedList содержит ссылку на тип класса узла.

class LinkedList 
{ 
    Node head;  
      class Node 
    { 
        int data; 
        Node next; 
           
        // Конструктор для создания ноды
        // Инициализируется по умолчанию как null
        Node(int d) {data = d;} 
    } 
}

Давайте создадим простой связный список на Java с тремя узлами

class LinkedList 
{ 
    Node head;  // голова списка
  
    static class Node { 
        int data; 
        Node next; 
        Node(int d)  { data = d;  next=null; } // конструктор
    } 
  
    /* метод, создающий простой связный список на Java с тремя узлами */
    public static void main(String[] args) 
    { 
        /* начинаем с пустого списка. */
        LinkedList llist = new LinkedList(); 
  
        llist.head  = new Node(1); 
        Node second = new Node(2); 
        Node third  = new Node(3); 
  
        /* Три узла распределены динамически. 
          У нас есть ссылки на эти три блока, как первый,   
          второй и третий
  
          llist.head        second              third 
             |                |                  | 
             |                |                  | 
         +----+------+     +----+------+     +----+------+ 
         | 1  | null |     | 2  | null |     |  3 | null | 
         +----+------+     +----+------+     +----+------+ */
  
        llist.head.next = second; // связываем первый со вторым 
  
        /*  Теперь следующий из первого узла относится ко второму.  Так они 
            оба связаны. 
    
         llist.head        second              third 
            |                |                  | 
            |                |                  | 
        +----+------+     +----+------+     +----+------+ 
        | 1  |  o-------->| 2  | null |     |  3 | null | 
        +----+------+     +----+------+     +----+------+ */
  
        second.next = third; // ссылка второго узла на третий узел
  
        /*  Теперь следующий из второго узла относится к третьему.  Итак, все три 
            узлы связаны.  
         llist.head        second              third 
            |                |                  | 
            |                |                  | 
        +----+------+     +----+------+     +----+------+ 
        | 1  |  o-------->| 2  |  o-------->|  3 | null | 
        +----+------+     +----+------+     +----+------+ */
    } 
}