Строение списка

а1, аi-1, ai, аi+1, аn.

Список может быть реализован с помощью массива, или ссылок. Связать последовательность элементов определенного типа в список можно так, чтобы каждый элемент содержал ссылку на следующий элемент последовательности. Такой список называется

однонаправленным. Если каждый элемент списка содержит две ссылки

(одну

на следующий элемент в списке, а вторую на предыдущий), то такой список называется

двунаправленным. Если же последний элемент связать ссылкой с первым, то получится кольцевой список.

Связный список (последовательность элементов одного типа)

Плюсы: последовательный доступ, добавление и удаление элементов.

Минусы: память, произвольный доступ, поиск.

Классический список

Устройство

голова хвост

100 120 222

5, 7, 12

Посмотреть хранящиеся значения можно только у head.

4 операции:

· Получить (изменить Head)

· Добавить Head

· Получить Tail

· Проверка на пустоту

class List<T>

{

class ListItem<T>

{

public T Data {get; set;}

public ListItem<T> Next {get; set;}

}

}

private ListItem<T> first;

private ListItem<T> current;

void AddFirst(T item);

T Current {get; set;}

bool HasValues {get;}

bool MoveNext();

void Reset();

public void AddFirst(T item)

{ if( first==null)

{ first=new.ListItem<T>()

{ Data=item};

}

else

{ current=new ListItem<T>() {Data=item};

current.Next=first;

first=current;

}

Список:

Плюсы: добавление и удаление элементов за const время

Минусы: на каждый элемент тратится дополнительное место на хранение ссылок; неизвестно положение элементов в памяти; необходим полный перебор для поиска, невозможен произвольный доступ по индексу; невозможно движение в обратном направлении.