Двусвязные и кольцевые списки

Else

Else

if (p == null)

result.head = q;

result.head = p;

return result;

}

Линейные односвязные списки, содержащие только один указатель — на следующий элемент, позволяют двигаться лишь в одном направлении — от начала списка к его концу. Можно построить список, каждый элемент которого содержит два указателя: на следующий элемент и на предыдущий. В этом случае описание типов и переменных будет таким:

Листинг 8.15. Узел для двухсвязного списка

class MyNode2

{

public int inf;

public MyNode2 next;

public MyNode2 pred;

// Конструктор

public MyNode2(int inf,MyNode2 next,MyNode2 pred)

{

this.inf = inf;

this.next = next; // на следующий элемент

this.pred = pred; // на предыдущий элемент

}

}

Движение по такому списку может происходить в двух направлениях: от начала к концу — с использованием указателя Next, и от конца к началу, используя указатель Pred. Пример двусвязного списка показан на рис. 8.8.

Рис. 8.8. Двусвязный список

Очевидно, что значение поля Next последнего элемента и поля Pred первого элемента линейного двусвязного списка равны null.

Добавление:

Листинг 8.16. Метод добавления

public void Add(int inf) // Add

{ // создание нового элемента

MyNode2 p = new MyNode2(inf, head, null);

if (head != null)

head.pred = p;

head = p;

count++;

}

Поиск:

Листинг 8.17. Поиск узла по значению

public MyNode2 FindNode(int inf)

{

MyNode2 p = head;

bool ok = false;

while ((p != null) && !ok)

{

ok = p.inf == inf;

if (!ok)

p = p.next;

}

return p;

}

Включение нового элемента в двусвязный список и удаление элемента происходит и проще, и сложнее, чем в односвязный. Проще — потому что элемент двусвязного списка содержит указатели и на следующий, и на предыдущий элементы, и нет нужды, как при вставке в односвязный список, либо обменивать информационные поля местами, либо тащить, при проходе по списку, дополнительный указатель на предыдущий элемент. Сложнее — потому что требуется переприсвоить и значения указателей Next, и значения указателей Pred. На рис. 8.9 показана вставка элемента в двусвязный список. Прежние значения указателей показаны светло-серым цветом.

Рис. 8.9. Вставка элемента в двусвязный список

Для того чтобы вставить в список новый элемент после элемента p (см. рис. 8.9), необходимы следующие действия:

Листинг 78.18. Вставка после p

public void Insetr(MyNode2 p, int inf)

{

MyNode2 q = new MyNode2(inf,p.next,p);

if (p.next != null)

p.next.pred = q;

p.next = q;

}

Удаление элемента p из двусвязного списка показано на рис. 8.10.

Рис. 8.10. Удаление элемента из двусвязного списка

Удаление производится следующими действиями:

· связать предыдущий элемент со следующим за p;

· связать следующий за p элемент с предыдущим.

Листинг 8.19. Удаление узла p

public void Delete(MyNode2 p)

{

if (p.next != null)

p.next.pred = p.pred;

if (p.pred != null)

p.pred.next = p.next;

Дата добавления: 2014-03-11; просмотров: 522; Нарушение авторских прав

Мы поможем в написании ваших работ!