Лекция
Привет, сегодня поговорим про двусвязные списки анимированые ы сравнение списков, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое двусвязные списки анимированые ы сравнение списков, массивов , настоятельно рекомендую прочитать все из категории Структуры данных.
. Об этом говорит сайт https://intellect.icuВ отличие от односвязных линейных списков, двусвязные, помимо полей data и next, имеют поле prev (указатель на предыдущий элемент списка):
type
Node<T> = class
data: T;
prev, next: Node<T>;
constructor (d: T; p, n: Node<T>);
begin
data := d;
prev := p;
next := n;
end;
end;
В случае двусвязного списка нам достаточно иметь ссылку на любой узел, тогда все остальные можно найти. Однако, для удобства, будем считать, что у нас есть две ссылки:
Удаление первого элемента списка
+-------+ +-------+ +-------+
\/\/\->|данные | |данные | |данные |
+---+---+ +---+---+ +---+---+
| 0 | |--->| | |--->| | 0 |
+---+-A-+ +-|-+-A-+ +-|-+---+
|________| |________|
превращается в
+-------+ +-------+ +-------+
|удален | \/\/\->|данные | |данные |
+---+---+ +---+---+ +---+---+
| 0 | 0 | | 0 | |--->| | 0 |
+---+---+ +---+-A-+ +-|-+---+
|________|
Удаление элемента из середины списка
+-------+ +-------+ +-------+
\/\/\->|данные | |данные | |данные |
+---+---+ +---+---+ +---+---+
| 0 | |--->| | |--->| | 0 |
+---+-A-+ +-|-+-A-+ +-|-+---+
|________| |________|
превращается в
___________________
| |
+-------+ | +-------+ +---V---+
\/\/\->|данные | | |удален | |данные |
+---+---+ | +---+---+ +---+---+
| 0 | |-' | 0 | 0 |--->| | 0 |
+---+-A-+ +---+---+ +-|-+---+
|_____________________|
Удаление первого элемента списка
+-------+ +-------+ +-------+
\/\/\->|данные | |данные | |данные |
+---+---+ +---+---+ +---+---+
| 0 | |--->| | |--->| | 0 |
+---+-A-+ +-|-+-A-+ +-|-+---+
|________| |________|
превращается в
+-------+ +-------+ +-------+
\/\/\->|данные | |данные | |удален |
+---+---+ +---+---+ +---+---+
| 0 | |--->| | 0 |--->| 0 | 0 |
+---+-A-+ +-|-+---+ +---+---+
|________|
|
Рис. 22.7. Удаление элемента двусвязного списка
Замечание. При выполнении любой операции нужно следить за возможными изменениями head и tail.
head := nil; tail := nil;
Примечание. Если изначально список был пуст, после добавления элемента надо не забыть сделать tail указывающим на него.
head := new Node<T>(0, nil, head); if head.next <> nil then head.next.prev := head else // если список был пуст tail := head;
tail := new Node<T>(2, tail, nil); if tail.prev <> nil then tail.prev.next := tail else // если список был пуст head := tail;
head := head.next; if head = nil then tail := nil else head.prev := nil;
tail := tail.prev; if tail = nil then head := nil else tail.next := nil;
if cur = head then // вставка в начало else begin cur.prev := new Node<T>(3, cur.prev, cur); cur.prev.prev.next := cur.prev; end;
if cur = tail then // вставка в конец else begin cur.next := new Node<T>(3, cur, cur.next); cur.next.next.prev := cur.next; end;
if cur = head then // удаление из начала else if cur = tail then // удаление из конца else begin cur.prev.next := cur.next; cur.next.prev := cur.prev; cur := cur.next; end;
Пример.
Дан двусвязный линейный список с целыми значениями.
Удалить все его отрицательные элементы.
var list: DoublyLinkedList<integer>;
// создание списка
var cur := list.head;
while cur <> nil do
if cur.data < 0 then
cur := list.RemoveAt(cur)
else
cur := cur.next;
type
Node<T> = class
data: T;
prev, next: Node<T>;
constructor (d: T; p, n: Node<T>);
begin
data := d;
prev := p;
next := n;
end;
end;
DoubleLinkedList<T> = class
head, tail: Node<T>;
constructor;
begin
head := nil;
tail := nil;
end;
procedure AddFirst(d: T);
begin
head := new Node<T>(d, nil, head);
if head.next <> nil then
head.next.prev := head
else // если список был пуст
tail := head;
end;
procedure AddLast(d: T);
begin
tail := new Node<T>(d, tail, nil);
if tail.prev <> nil then
tail.prev.next := tail
else // если список был пуст
head := tail;
end;
procedure DeleteFirst;
begin
head := head.next;
if head = nil then
tail := nil
else
head.prev := nil;
end;
procedure DeleteLast;
begin
tail := tail.prev;
if tail = nil then
head := nil
else
tail.next := nil;
end;
procedure InsertBefore(cur: Node<T>; d: T);
begin
if cur = head then
AddFirst(d)
else
begin
cur.prev := new Node<T>(d, cur.prev, cur);
cur.prev.prev.next := cur.prev;
end;
end;
procedure InsertAfter(cur: Node<T>; d: T);
begin
if cur = tail then
AddLast(d)
else
begin
cur.next := new Node<T>(d, cur, cur.next);
cur.next.next.prev := cur.next;
end;
end;
function RemoveAt(cur: Node<T>): Node<T>;
begin
if cur = head then
begin
DeleteFirst;
Result:=head;
end
else if cur = tail then
begin
DeleteLast;
Result:=nil;
end
else if cur = tail then
begin
DeleteLast;
result := nil;
end
else
begin
cur.prev.next := cur.next;
cur.next.prev := cur.prev;
result := cur.next;
end;
end;
procedure Print;
begin
var cur := head;
while cur <> nil do
begin
writeln(cur.data);
cur := cur.next;
end;
end;
procedure PrintReverse;
begin
var cur := tail;
while cur <> nil do
begin
writeln(cur.data);
cur := cur.prev;
end;
end;
end;
по количеству операция (n - кол-во элементов)
| Массив | Список | |
|---|---|---|
| Вставка в конец, удаление из конца |  |
|
| Вставка в начало, удаление из начала |  |
|
| Вставка в середину, удаление из середины | |
|
| Проход | |
|
| Доступ по индексу | |
 |
| Поиск | |
|
Надеюсь, эта статья про двусвязные списки анимированые ы сравнение списков, была вам полезна, счастья и удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое двусвязные списки анимированые ы сравнение списков, массивов и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных
Из статьи мы узнали кратко, но содержательно про двусвязные списки анимированые ы сравнение списков
Комментарии
Оставить комментарий
Структуры данных
Термины: Структуры данных