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

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) пази множество листове в един динамичен масив. Нея ще разгледаме малко по-нататък, в тази тема.

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

  1. Информация за абстрактния тип Лист (en.wikipedia.org)
  2. Структурата данни List в STL (www.cplusplus.com)
  3. Опашка (www.informatika.bg)


За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 5058 пъти.

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

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

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