Hi there! Our project relies on ads or donation to keep the site free to use. Please sending a donation . Thanks!
Подождите, пожалуйста, выполняется поиск в заданном разделе

Двусвязные списки. Анимированые примеры. Сравнение списков и массивов

Двусвязные списки. Анимированые примеры. Сравнение списков и массивов

Привет, сегодня поговорим про двусвязные списки анимированые ы сравнение списков, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое двусвязные списки анимированые ы сравнение списков,массивов , настоятельно рекомендую прочитать все из категории Алгоритмы и структуры данных

. Об этом говорит сайт 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;

В случае двусвязного списка нам достаточно иметь ссылку на любой узел, тогда все остальные можно найти. Однако, для удобства, будем считать, что у нас есть две ссылки:

  • head — на начало списка (start ptr)
  • tail — на конец списка (end ptr)

 

Удаление первого элемента списка
                                   
       +-------+    +-------+    +-------+  
\/\/\->|данные |    |данные |    |данные |
       +---+---+    +---+---+    +---+---+
       | 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;




  • Добавление элемента в конец 

 

  • Удаление элемента из начала 

 

  • Удаление элемента из конца 

 

 

 

  • Вставка элемента перед текущим 

 

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;

  • Удаление текущего 

 

 

 

Пример
Дан двусвязный линейный список с целыми значениями. 
Удалить все его отрицательные элементы.

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;


Создадим класс двусвязный линейный список, полями которого будут head и tail:

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 - кол-во элементов)

  Массив Список
Вставка в конец, удаление из конца
Вставка в начало, удаление из начала
Вставка в середину, удаление из середины
Проход
Доступ по индексу
Поиск

Понравилась статья о двусвязные списки анимированые ы сравнение списков? Откомментируйте её Надеюсь, что теперь ты понял что такое двусвязные списки анимированые ы сравнение списков,массивов и для чего все это нужно, а если не понял, или есть замечания, то нестесняся пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятелно рекомендую изучить комплексно всю информацию в категории Алгоритмы и структуры данных


Комментарии (0)


Оставить комментарий

ответить

Структуры данных

Термины: Структуры данных