Связанный список. Цепочка указателей. Добавление новых элементов в список. Получение содержимого списка

Связанный список
Связный список тоже предназначен для хранения данных. До сих пор мы рассматривали как пример структур для хранения данных лишь массивы и массивы указателей на данные (в примерах PTRTOSTRS и PTROBJS). Недостатком обеих этих структур является необходимость объявлять фиксированное значение размера массива до запуска программы.

Цепочка указателей

Связный список представляет собой более гибкую систему для хранения данных,в которой вовсе не используются массивы. Вместо них мы получаем для каждого элемента память, используя операцию new, а затем соединяем (или связываем) элементы данных между собой, используя указатели. Элементы списка не обязаны храниться в смежных участках памяти, как это происходит с массивами; они могут быть разбросаны по всему пространству памяти

В нашем примере связный список является объектом класса linkList. Элементы списка представлены структурой link. Каждый элемент содержит целое число, представляющее собой данные, и указатель на следующий элемент списка. Указатель на сам список хранится в начале списка.

// linklist.cpp

// список

#include <iostream>

using namespace std;

///////////////////////////////////////////////////////////

struct link // один элемент списка

{

int data; // некоторые данные

link* next; // указатель на следующую структуру

};

///////////////////////////////////////////////////////////

class linklist // список

{

private:

link* first;

public:

linklist () // конструктор без параметров

{ first = NULL; } // первого элемента пока нет

void additem (int d); // добавление элемента

void display (); // показ данных

};

///////////////////////////////////////////////////////////

void linklist::additem (int d) // добавление элемента

{

link* newlink = new link; // выделяем память

newlink->data = d; // запоминаем данные

newlink->next = first; // запоминаем значение first

first = newlink; // first теперь указывает на новый элемент

}

///////////////////////////////////////////////////////////

void linklist::display ()

{

link* current = first; // начинаем с первого элемента

while(current) // пока есть данные

{

cout << current->data << endl; // печатаем данные

current = current->next; // двигаемся к следующему элементу

}

}

///////////////////////////////////////////////////////////

int main ()

{

linklist li; // создаем переменную-список

li.additem (25); // добавляем туда несколько чисел

li.additem (36);

li.additem (49);

li.additem (64);

li.display (); // показываем список

return 0;

}

Класс linklist имеет только одно поле: указатель на начало списка. При создании списка конструктор инициализирует этот указатель, именованный как first, значением NULL, которое аналогично значению 0. Это значение является признаком того, что указатель указывает на адрес, который точно не может содержать полезной информации. В нашей программе элемент, указатель которого на следующий элемент имеет значение NULL, является конечным элементом списка.

Добавление новых элементов в список

Функция additem() позволяет нам добавить новый элемент в связный список. Новый элемент вставляется в начало списка (мы могли бы вставлять новый элемент и в конец списка, но это будет более сложным примером). Давайте последовательно рассмотрим действия при вставке нового элемента. Сначала мы создаем новый элемент типа link в строке

link* newlink = new link;

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

Затем мы заполняем элемент нужным нам значением. При этом действия со структурой похожи на действия с классами; к элементам структуры можно получить доступ, используя операцию ->. В следующих двух строках программы мы присваиваем переменной data значение, переданное как аргумент функции additem(), а указателю на следующий элемент мы присваиваем значение, хранящееся в указателе first. Этот указатель содержит в себе адрес начала списка.

newlink->data = d;
newlink->next = first;

И в заключение мы присваиваем указателю first значение указателя на новый элемент списка,

first = newlink;

Смыслом всех этих действий является замена адреса, содержащегося в указателе first, на адрес нового элемента, при этом старый адрес указателя first превратится в адрес второго элемента списка.

Получение содержимого списка

Когда список уже создан, легко получить хранящиеся в нем значения (или выполнить операции с ними). Все, что нам нужно, это следовать от одного указателя next к другому до тех пор, пока его значение не станет равным NULL, означающим конец списка. В строке функции display()

cout << endl << current=data;

выводится значение, содержащееся в переменной data, и

current = current->next;

перемещает нас к следующему элементу списка до тех пор, пока

current!= NULL;

выражение условия в операторе while не станет ложным. Вот результат работы
программы LINKLIST:

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

Поиск по сайту: