---
title: "Basic Data Structures: Linked List"
description: "Решил тут вспомнить что же такое структуры данных да алгоритмы. Помнится последний раз с этим сталки..."
author: "mshogin"
published: "2009-11-16T10:23:49+00:00"
modified: "2009-11-16T10:23:49+00:00"
locale: "ru"
canonical_url: "https://yvision.kz/post/basic-data-structures-linked-list-21990"
markdown_url: "https://yvision.kz/post/basic-data-structures-linked-list-21990/markdown"
site_name: "Yvision.kz"
---

# Basic Data Structures: Linked List

> Решил тут вспомнить что же такое структуры данных да алгоритмы. Помнится последний раз с этим сталки...

Решил тут вспомнить что же такое структуры данных да алгоритмы. Помнится последний раз с этим сталкивался еще в универе.

По работе особо и не приходится этим заниматься. Что не говори, а лучший провайдер алгоритмов - база данных. Мы уже настолько привыкли к этому, что если нас попросить сделать сортировку списка, мы будем кричать "Да я, да я! Да я два списка по 100000 записей сджойню и отсортирую в пять сек!"

А на деле что? Ну хорошо если полезешь на CPAN да скачаешь модуль который за тебя все это сделает, а если решишь сам все сделать?

Сколько интересно времени на все уйдет. Так что повторение, как говорится, мать учения.

Так что начнем с основ. Связной список.

** **

Сам придумывать не стал, честно спер с вики. Связной список - [структура данных](http://ru.wikipedia.org/wiki/%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85), состоящая из [узлов](http://ru.wikipedia.org/w/index.php?title=%D0%A3%D0%B7%D0%B5%D0%BB_%28%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0%29&action=edit&redlink=1), каждый из которых содержит как собственные [данные](http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%B5_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%28%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0%29), так и одну или две [ссылки](http://ru.wikipedia.org/w/index.php?title=%D0%A1%D1%81%D1%8B%D0%BB%D0%BA%D0%B0_%28%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0%29&action=edit&redlink=1) («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед [массивом](http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%81%D1%81%D0%B8%D0%B2) является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Интресно было сравнить различные списки.

Список построенный на массиве, хеше, объекте массиве и объекте хеше

В итоге получилось два объекта, практически идентичных. Ниже код объекта на основе хеша

** **

```
package LinkedListHash;use Data::Dumper;sub new{ my $class = shift; my $value = shift; $class = ref $class || $class; return bless { value => $value, next => undef }, $class;} sub add{ my $self = shift; my $item = shift; my $obj = (ref $self)->new($item); $self->tail->{next} = $obj; return $self;} sub tail{ my $self = shift; my $next = $self; while ( $next->{next} ){ $next = $next->{next} } return $next;} sub find{ my $self = shift; my $val = shift; my $cmp = shift; for(my $next = $self; $next; $next = $next->{next}){ return $next if $cmp->($next->{value}, $val) == 0 ; } return undef;} sub insertAfter{ my $self = shift; my $item = shift; my $newItem = shift; if($item->{next}){ my $obj = (ref $self)->new($newItem); $obj->{next} = $item->{next}; $item->{next} = $obj; } else{ $item->next = (ref $self)->new($newItem); } return $self;} sub removeAfter{ my $self = shift; my $item = shift; return $self unless $item->{next}; if($item->{next}->{next}){ my $obj = $item->{next}->{next}; $item->{next} = $obj; } else{ $item->{next} = undef; } return $self;} sub DESTROY{ my $self = shift; #warn Dumper($self->{value});}1;
```

**Сравнивал используя Benchmark.**

**В сравнении участвовали функции создания списка и поиска элемента.**

**Вставка и удаление делаются за O(1), без учета поиска.**

**Поиск элемента занимает O(N) операций.**

** **

**Скрипт оценки производительности создания списка:**

```
use LinkedListHash;use LinkedListArr;use Benchmark qw(:all) ; my $count = 100; timethese($count, { 'Object Hash' => \&hash_fill,'Object Array' => \&array_fill,'Pure Hash' => \&pure_hash_fill,'Pure Array' => \&pure_array_fill,}); sub hash_fill{ my $item = {val1 => 1, val2 => 2}; my $list = new LinkedListHash($item); for (my $i = 3; $i <>add( {val1 => $i, val2 => $i+1 } ); }} sub array_fill{ my $item = {val1 => 1, val2 => 2}; my $list = new LinkedListArr($item); for (my $i = 3; $i <>add( {val1 => $i, val2 => $i+1 } ); }} sub pure_array_fill{ my ($tail, $list); for (my $i = 1; $i <>[0] = [ undef, {val1 => $i, val2 => $i+1 } ]; $tail = $tail->[0]; } else { $list = $tail = [ undef, {val1 => $i, val2 => $i+1 } ]; } }} sub pure_hash_fill{ my ($tail, $list); for (my $i = 1; $i <>{next} = { next => undef, val => {val1 => $i, val2 => $i+1 } }; $tail = $tail->{next}; } else { $list = $tail = { next => undef, val => {val1 => $i, val2 => $i+1 } }; } }}
```

И результаты:

Benchmark: timing 100 iterations of Object Array, Object Hash, Pure Array, Pure Hash...

Object Array: 28 wallclock secs (27.88 usr + 0.00 sys = 27.88 CPU) @ 3.59/s (n=100)

Object Hash: 32 wallclock secs (30.97 usr + 0.00 sys = 30.97 CPU) @ 3.23/s (n=100)

Pure Array: 6 wallclock secs ( 5.32 usr + 0.00 sys = 5.32 CPU) @ 18.80/s (n=100)

Pure Hash: 7 wallclock secs ( 7.24 usr + 0.00 sys = 7.24 CPU) @ 13.81/s (n=100)

Результаты конечно предсказуемы, но что бы настолько - я был очень удивлен. Причем, если создавать не 10000 элементов в не объектных списках, а 999 то получаем

- (warning: too few iterations for a reliable count)

Далее оценим поиск элемента

Скрипт оценки производительности

```
use LinkedListHash;
```

```
use LinkedListArr;use Data::Dumper;use Benchmark qw(:all) ; my $count = 10000; our $ho_list = &hash_fill;our $ao_list = &array_fill;our $ph_list = &pure_hash_fill;our $pa_list = &pure_array_fill; our $find_val = 9; timethese($count, { 'object Hash Find' => \&hash_find, 'object Array Find' => \&array_find, 'pure Hash Find' => \&pure_hash_find, 'pure Array Find' => \&pure_array_find,}); sub hash_find{ my $fitem = $ho_list->find($find_val, \&compare);} sub array_find{ my $fitem = $ao_list->find($find_val, \&compare);} sub pure_hash_find{ my $item = $ph_list; while ($item){ last if ::compare->($item->{val}, $find_val) == 0; $item = $item->{next}; }} sub pure_array_find{ my $item = $pa_list; while ($item){ last if ::compare->($item->[1], $find_val) == 0; $item = $item->[0]; }} sub compare{ return $_[0]->{val1} > $_[1] ? 1 : $_[0]->{val1} < $_[1] ? -1 : 0;
```

```
}
```

Замеры делались для поиска элементов в начале, середине и конце списка

our $find_val = 9;

Benchmark: timing 10000 iterations of object Array Find, object Hash Find, pure Array Find, pure Hash Find...

object Array Find: 0 wallclock secs ( 0.19 usr + 0.00 sys = 0.19 CPU) @ 53191.49/s (n=10000)

(warning: too few iterations for a reliable count)

object Hash Find: 0 wallclock secs ( 0.19 usr + 0.00 sys = 0.19 CPU) @ 53475.94/s (n=10000)

(warning: too few iterations for a reliable count)

pure Array Find: 1 wallclock secs ( 0.19 usr + 0.00 sys = 0.19 CPU) @ 53475.94/s (n=10000)

(warning: too few iterations for a reliable count)

pure Hash Find: 0 wallclock secs ( 0.19 usr + 0.00 sys = 0.19 CPU) @ 53475.94/s (n=10000)

(warning: too few iterations for a reliable count)

our $find_val = 550;

Benchmark: timing 10000 iterations of object Array Find, object Hash Find, pure Array Find, pure Hash Find...

object Array Find: 10 wallclock secs (10.37 usr + 0.00 sys = 10.37 CPU) @ 963.95/s (n=10000)

object Hash Find: 10 wallclock secs (10.97 usr + 0.00 sys = 10.97 CPU) @ 911.91/s (n=10000)

pure Array Find: 10 wallclock secs (10.54 usr + 0.00 sys = 10.54 CPU) @ 948.32/s (n=10000)

pure Hash Find: 11 wallclock secs (11.22 usr + 0.00 sys = 11.22 CPU) @ 891.58/s (n=10000)

our $find_val = 996;

Benchmark: timing 10000 iterations of object Array Find, object Hash Find, pure Array Find, pure Hash Find...

object Array Find: 20 wallclock secs (19.25 usr + 0.01 sys = 19.27 CPU) @ 519.08/s (n=10000)

object Hash Find: 21 wallclock secs (20.58 usr + 0.02 sys = 20.59 CPU) @ 485.63/s (n=10000)

pure Array Find: 20 wallclock secs (19.55 usr + 0.03 sys = 19.58 CPU) @ 510.78/s (n=10000)

pure Hash Find: 21 wallclock secs (20.23 usr + 0.00 sys = 20.23 CPU) @ 494.22/s (n=10000)

Собственно поиск получается довольно таки стабильным и равномерным.

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

---

Source: [https://yvision.kz/post/basic-data-structures-linked-list-21990](https://yvision.kz/post/basic-data-structures-linked-list-21990)