Связный список

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1] Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Виды связных списков[править | править вики-текст]

Линейный связный список[править | править вики-текст]

Односвязный список (Однонаправленный связный список)[править | править вики-текст]

Single linked list.png

Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.

Двусвязный список (Двунаправленный связный список)[править | править вики-текст]

Doubly linked list.png

Здесь ссылки в каждом узле указывают на предыдущий и на последующий узел в списке. По двусвязному списку можно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.

XOR-связный список[править | править вики-текст]

Кольцевой связный список[править | править вики-текст]

Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.

Односвязный кольцевой список

Реализация такой структуры происходит на базе линейного списка. В каждом кольцевом списке есть указатель на первый элемент. В этом списке константы NULL не существует.

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

Список с пропусками[править | править вики-текст]

Развёрнутый связный список[править | править вики-текст]

Пример реализации на Java[править | править вики-текст]

public class Node {
  //содержимое текущего элемента списка
  private int element;
  //указатель на следующий элемент списка
  private Node next;
  //вывод содержимого текущего элемента
  public int getElement(){
    return element;
  }
  //установка содержимого для текущего элемента списка
  public void setElement(int e){
    element = e;
  }
  //получение указателя на следующий элемент списка
  public Node getNext() {
    return next;
  }
  //установка следующего элемента списка
  public void setNext(Node n) {
    next = n;
  }
}

Пример реализации односвязного списка на C#[править | править вики-текст]

class Node
    {
        public void SetNextNode(Node _nextNode)
        {
            this.next = _nextNode;
        }
        public int Element
        { 
            get
            {
                return this.element;
            }
            set
            {
                this.element = value;
            }
        }
 
        public Node Next
        {
            get
            {
                return this.next;
            }
        }
 
        private Node next;
        private int element;
    }
 
class List
    {
        public List()
        {
            // создание пустого списка
            this.headNode = null;
            this.tailNode = this.headNode;
            this.Length = 0;
        }
        public void Push(int _element)
        {
            if (headNode == null)
            {
                // создать узел, сделать его головным
                this.headNode = new Node();
                this.headNode.Element = _element;
                // этот же узел и является хвостовым
                this.tailNode = this.headNode;
                // следующего узла нет
                this.headNode.SetNextNode(null);
            }
            else
            {
                // создать временный узел
                Node newNode = new Node();
                // следующий за предыдущим хвостовым узлом - это наш временный новый узел
                this.tailNode.SetNextNode(newNode);
                // сделаь его же новым хвостовым
                this.tailNode = newNode;
                this.tailNode.Element = _element;
                // слудующего узла пока нет
                this.tailNode.SetNextNode(null);
            }
 
            ++this.Length;
        }
        public int this[int _position]
        {
            get
            {
                // дабы не загромождать пример, 
                // опустим проверку на валидность переданного параметра '_position'
                Node tempNode = this.headNode;
                for (int i = 0; i < _position; ++i)
                    // переходим к следующему узлу списка
                    tempNode = tempNode.Next;
                return tempNode.Element;
            }
        }
 
        public int Length { get; private set; }
        private Node headNode;
        private Node tailNode;
    }

Достоинства[править | править вики-текст]

  • лёгкость добавления и удаления элементов
  • размер ограничен только объёмом памяти компьютера и разрядностью указателей
  • динамическое добавление и удаление элементов

Недостатки[править | править вики-текст]

  • сложность определения адреса элемента по его индексу (номеру) в списке
  • на поля-указатели (указатели на следующий и предыдущий элемент) расходуется дополнительная память (в массивах, например, указатели не нужны)
  • работа со списком медленнее, чем с массивами, так как к любому элементу списка можно обратиться, только пройдя все предшествующие ему элементы
  • элементы списка могут быть расположены в памяти разреженно, что окажет негативный эффект на кэширование процессора
  • над связными списками гораздо труднее (хотя и в принципе возможно) производить параллельные векторные операции, такие как вычисление суммы
  • кэш-промахи при обходе списка

Примечания[править | править вики-текст]

  1. Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 2nd edition. The MIT Press, 2001. ISBN 0-262-03293-7

См. также[править | править вики-текст]