Свързан списък

Linked List

В тази тема ще разгледаме какво е свързан списък, какви операции поддържа и с каква сложност е всяка от тях. Ще видим как се имплементира двусвързан списък и ще дадем цялостна имплементация като шаблонен клас, както и код, с който да тествате ваша такава.

Автор: Александър Георгиев

Вече видяхме един начин, по който можем да пазим неизвестен брой елементи. Съществува и друга, много известна структура данни, която върши това.

Списък

Структурата данни "Свързан списък" представлява поредица от елементи, като всеки от тях съдържа не само информацията, която бихме пазили в масив, ами и информация кой е следващият елемент в поредицата. В най-стандартната имплементация, тази информация представлява указател към следващия елемент. Така лесно можем да обходим всички елементи от структурата - почвайки от първия, следваме неговия указател към следващия, от там към по-следващия и т.н. Допълнително ще пазим два указателя - към първия и към последния елемент на списъка - което ни позволява лесно да добавяме елемент както в началото, така и в края на списъка.

Предимства

Можем бързо да добавяме елемент (с O(1)) както в началото, така и в края на списъка. При масивите добавянето в края беше също константна операция, но в началото отнемаше цели O(N) стъпки.
С O(1) можем да добавим елемент и на произволна позиция по средата на списъка, стига вече да имаме указател, сочещ към елемента преди или след тази позиция.
Можем да поддържаме паметта точно колкото ни трябва (без "резервни" клетки) като сложността на добавяне си остава O(1).

Недостатъци

Най-големият недостатък в сравнение с масивите е, че губим възможността за произволен достъп. Няма начин, по който да индексираме k-тия елемент, без да минем през всички k-1 предходни. Това прави операции като сортиране, двоично търсене и т.н. невъзможни, или поне неприемливо бавни.
Тъй като всяка клетка от списъка съдържа указател към следващата клетка, то всеки елемент заема повече памет, отколкото би заемала клетката в масив. Когато информацията във всяка клетка е относително много, това не е проблем, но ако просто пазим по един int, то ние ще се нуждаем от поне двойно повече памет. Нашата имплементация ще е двусвързан списък, тоест ще имаме и още един указател към предходния елемент в списъка, което прави нещата дори по-зле в това отношение.
Заделяме памет при всяко добавяне на нов елемент, което може да бъде сравнително бавно.
Копирането е учудващо сложно.

Кога бихме ползвали списък пред масив?

Сравнително рядко, но все пак има случаи, в които списъкът е по-удачен избор от динамичен масив. Един вариант е когато наистина ни трябва да пестим паметта възможно най-много и все пак да имаме бързо добавяне на елементи.

В състезателното програмиране списъците се ползват доста рядко, като на този сайт ще ги ползваме само в един от вариантите на представяне на графи. Даже там ще ползваме хибрид между свързан списък и динамичен масив - ще заделяме по много клетки наведнъж, както правихме при динамичния масив, за да избегнем бавнотата на заделянето на памет.

Имплементация

Следва да покажем примерна имплементация на двусвързан списък, с основните операции за добавяне в началото и края, търсене и взимане на k-тия елемент.

Единична клетка

Освен информацията (която отново ще е темплейтен тип DataType), всяка клетка ще съдържа указател към предходната и следващата клетка в списъка. Ще енкапсулираме тези данни в структура Element.

typedef
 int
 DataType;

struct Element {
    DataType data;
    Element *
prev,
 *
next;
    Element(const
 DataType& value) {
        data =
 value;
        prev =
 next =
 NULL
;
    }
};

Данни

Ще ни трябват един указател към първата клетка (наричана глава или head), един указател към последната клетка (наричана опашка или tail, и един int, който да пази общия брой клетки. Забележете, че този брояч реално не ни трябва, но ще го пазим за да можем да изпълняваме метода size() с O(1)).

struct List {
    int
 size;
    Element *
head,
 *
tail;
};

Инициализация

В началото броят елементи в списъка е нула, а двата указателя (за начало и край) не сочат никъде.

void
 init(List& list) {
    list.size =
 0
;
    list.head =
 list.tail =
 NULL
;
}

size()

Връща колко елемента има в списъка. Тук допълнителната променлива size ни помага да извършваме тази операция с O(1). Всъщност не се нуждаем от функция за това (поне при тази имплементация), можем директно да ползваме list.size в кода си.

int
 size(List& list) {
    return
 list.size;
}

empty()

Показва дали списъкът е празен. Отново, можем да минем и без тази функция.

bool
 empty(List& list) {
    return
 !
list.size;
}

front()

Връща първия елемент от списъка. Спира програмата ако списъкът е празен (тогава тази операция е невалидна).

DataType&
 front(List& list) {
    assert(list.size >
 0
);
    return
 list.head-
>
data;
}

back()

Връща последния елемент от списъка. Спира програмата ако списъкът е празен (тогава тази операция е невалидна).

DataType&
 back(List& list) {
    assert(list.size >
 0
);
    return
 list.tail-
>
data;
}

at()

Връща елемента на позиция index. Спира програмата ако индексът е по-малък от нула или по-голям или равен на броя елементи на списъка (тогава тази операция е невалидна).

DataType&
 at(List&
 list,
 int index) {
    assert(index >
=
 0
 &
&
 index <
 list.size);
    Element*
 link =
 list.head;
    for
 (int
 i =
 0
;
 i <
 index;
 i+
+)
        link =
 link-
>
next;
    return
 link-
>
data;
}

push_front()

Добавя елемент в началото на списъка.

void
 push_front(List&
 list,
 const
 DataType& value) {
    Element*
 element =
 new
 Element(value);
    element-
>
next =
 list.head;
    if
 (list.size =
=
 0)
        list.head =
 list.tail =
 element;
    else
        list.head =
 list.head-
>
prev =
 element;
    list.size+
+
;
}

push_back()

Добавя елемент в края на списъка.

void
 push_back(List&
 list,
 const
 DataType& value) {
    Element*
 element =
 new
 Element(value);
    element-
>
prev =
 list.tail;
    if
 (list.size =
=
 0)
        list.head =
 list.tail =
 element;
    else
        list.tail =
 list.tail-
>
next =
 element;
    list.size+
+
;
}

insert()

Добавя елемент на позиция index или в началото/края на списъка, ако позицията е преди/след първия/последния елемент.

void
 insert(List&
 list,
 int
 index,
 const
 DataType& value) {
    if
 (index <
=
 0) {
        push_front(list,
 value);
    }
    else
 if
 (index >
= list.size) {
        push_back(list,
 value);
    }
    else {
        Element*
 link =
 list.head;
        for
 (int
 i =
 0
;
 i <
 index -
 1
;
 i+
+)
            link =
 link-
>
next;
        Element*
 element =
 new
 Element(value);
        element-
>
prev =
 link;
        element-
>
next =
 link-
>
next;
        element-
>
prev-
>
next =
 element;
        element-
>
next-
>
prev =
 element;
        list.size+
+
;
    }
}

pop_front()

Премахва първия елемент от списъка, ако такъв съществува.

void
 pop_front(List& list) {
    if
 (list.size =
=
 0)
        return
;
    if
 (list.size =
=
 1) {
        delete
 list.head;
        list.head =
 list.tail =
 NULL
;
    }
    else {
      Element*
 link =
 list.head;
      list.head =
 link-
>
next;
      list.head-
>
prev =
 NULL
;
      delete
 link;
    }
    list.size-
-
;
}

pop_back()

Премахва последния елемент от списъка, ако такъв съществува.

void
 pop_back(List& list) {
    if
 (list.size =
=
 0)
        return
;
    if
 (list.size =
=
 1) {
        delete
 list.head;
        list.head =
 list.tail =
 NULL
;
    }
    else {
        Element*
 link =
 list.tail;
        list.tail =
 link-
>
prev;
        list.tail-
>
next =
 NULL
;
        delete
 link;
    }
    list.size-
-
;
}

erase()

Изтрива даден елемент или интервал от елементи, зададени чрез индекс към първия и един след последния.

void
 erase(List&
 list,
 int
 first,
 int last) {
    first =
 (first <
 0
 ?
 0
 :
 first);
    int
 count =
 (last =
=
 -
1
 ?
 1
 :
 last -
 first);
    if
 (first >
=
 list.size |
|
 count <
=
 0)
        return
;

    Element*
 link =
 list.head;
    for
 (int
 i =
 0
;
 i <
 first;
 i+
+)
        link =
 link-
>
next;
    for
 (int
 i =
 0
;
 i <
 count &
&
 link !
=
 NULL
;
 i+
+) {
        if
 (list.head =
= link)
            list.head =
 link-
>
next;
        if
 (list.tail =
= link)
            list.tail =
 link-
>
prev;
        if
 (link-
>
prev !
=
 NULL)
            link-
>
prev-
>
next =
 link-
>
next;
        if
 (link-
>
next !
=
 NULL)
            link-
>
next-
>
prev =
 link-
>
prev;
        Element*
 next =
 link-
>
next;
        delete
 link;
        link =
 next;
        list.size-
-
;
    }
}

clear()

Изтрива всички елементи от списъка. Това е еквивалентно да erase()-нем от първия до последния елемент, което и всъщност ще направим за да не пишем кода наново.

void
 clear(List& list) {
    while
 (list.head !
=
 NULL) {
        Element*
 element =
 list.head;
        list.head =
 list.head-
>
next;
        delete
 element;
    }
    list.size =
 0
;
    list.head =
 list.tail =
 NULL
;
}

Цялостна имплементация

Цялостна имплементация и тестове: List.h | ListTester.cpp

Хибриден лист

Една интересна модификация на стандартния свързан списък, донякъде известна в българските състезателни среди като "структура на Велин" (тъй като Велин Цанов я преподаваше по време на подготовката на националите за IOI) пази множество листове в един динамичен масив. Нея ще разгледаме малко по-нататък, в тази тема.

Допълнителни материали

Страницата е посетена 18832 пъти.

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: