На нашем сайте мы используем cookie для сбора информации технического характера и обрабатываем IP-адрес вашего местоположения. Продолжая использовать этот сайт, вы даете согласие на использование файлов cookies. Здесь вы можете узнать, как мы пользуемся файлами cookies.
Я согласен
логотип upread.ru

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


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



Почему 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 | 
        +----+------+     +----+------+     +----+------+ */
    } 
}





тегизаметки, java, списки, связные списки

Читайте также:




Постепенное появление размытого изображения CSS
Липовый счетчик лиру: межстрочный интервал и наведение


© upread.ru 2013-2019
При перепечатке активная ссылка на сайт обязательна.
Задать вопрос
письмо
Здравствуйте! Вы можете задать мне любой вопрос. Если не получается отправить сообщение через эту форму, то пишите на почу up777up@yandex.ru
Отправляя сообщение я подтверждаю, что ознакомлен и согласен с политикой конфиденциальности данного сайта.