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

Виды связных списков

Линейный связный список

Односвязный список (Однонаправленный связный список)

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

Двусвязный список (Двунаправленный связный список)

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

XOR-связный список

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

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

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

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

Список с пропусками

Развёрнутый связный список

Пример реализации на С++

//Односвязный список
#include "stdafx.h"
#include "iostream"
 
using namespace std;
 
 
struct Value
{
        public:int data;
        Value* Next;
        Value(int d):Next(0),data(d){}
        ~Value(){data=0;}
};
 
class Stack
{
        Value* Head;
        public:void Add(int d);
        public:void Delete();
        public:void Print();
        public:Stack(){Head=NULL;}
};
 
void Stack::Add(int d)
{
        Value* newHead=new Value(d);    
        newHead->Next=Head;
        Head=newHead;
}
 
void Stack::Delete()
{
        Value *p;
        p=Head->Next;
        delete Head;
        Head=p;
}
 
 
void Stack::Print()
{
        Value *p=Head;
        while(p!=NULL)
        {
                cout<<p->data<<"  ";
                p=p->Next;
        }
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
        Stack elements;
 
        elements.Add(10);
        elements.Add(1);
        elements.Add(3);
        elements.Add(7);
        elements.Add(9);
        elements.Add(4);
 
        elements.Delete();
        elements.Delete();
 
        elements.Print();
 
        system("pause");
        return 0;
}

Пример реализации на 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;
  }
}

Достоинства

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

Недостатки

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

Примечания

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

См. также

• Список структур данных
• Стек
• Очередь
• Дерево
• Сортировка связного списка