08-08-2023
В информатике, свя́зный спи́сок — структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1] Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Содержание |
Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.
Здесь ссылки в каждом узле указывают на предыдущий и на последующий узел в списке. По двусвязному списку можно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.
Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.
Реализация такой структуры происходит на базе линейного списка. В каждом кольцевом списке есть указатель на первый элемент. В этом списке константы NULL не существует.
Также существуют циклические списки с выделенным головным элементом, облегчающие полный проход через список.
//Односвязный список #include "stdafx.h" #include "iostream" using namespace std; struct Value { public:int data; Value* Next; Value(int d):Next(0),data(d){} ~Value(){data=0;} }; class Stack { Value* Head; public:void Add(int d); public:void Delete(); public:void Print(); public:Stack(){Head=NULL;} }; void Stack::Add(int d) { Value* newHead=new Value(d); newHead->Next=Head; Head=newHead; } void Stack::Delete() { Value *p; p=Head->Next; delete Head; Head=p; } void Stack::Print() { Value *p=Head; while(p!=NULL) { cout<<p->data<<" "; p=p->Next; } } int _tmain(int argc, _TCHAR* argv[]) { Stack elements; elements.Add(10); elements.Add(1); elements.Add(3); elements.Add(7); elements.Add(9); elements.Add(4); elements.Delete(); elements.Delete(); elements.Print(); system("pause"); return 0; }
public class Node { private int element; private Node next; public int getElement(){ return element; } public void setElement(int e){ element = e; } public Node getNext() { return next; } public void setNext(Node n) { next = n; } }
Связный список.