Структура данных LinkedList

Содержание

Представление LinkedList
Утилита связанного списка
Реализации связанных списков в примерах Python, Java, C и C ++
Сложность связанного списка
Связанные списки приложений

В этом руководстве вы узнаете о структуре данных связанного списка и ее реализации на Python, Java, C и C ++.

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

Структура данных LinkedList

Вы должны с чего-то начать, поэтому мы даем адресу первого узла специальное имя HEAD.

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

Возможно, вы играли в игру «Охота за сокровищами», где каждая подсказка включает информацию о следующей подсказке. Так работает связанный список.

Представление LinkedList

Давайте посмотрим, как представлен каждый узел LinkedList. Каждый узел состоит:

Элемент данных
Адрес другого узла

Мы оборачиваем и элемент данных, и ссылку на следующий узел в структуру как:

 struct node ( int data; struct node *next; );

Понимание структуры узла связанного списка - ключ к пониманию этого.

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

 /* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data=3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;

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

Всего за несколько шагов мы создали простой связанный список с тремя узлами.

LinkedList Представление

Сила LinkedList заключается в возможности разорвать цепочку и снова присоединиться к ней. Например, если вы хотите поместить элемент 4 между 1 и 2, шаги будут такими:

Создайте новый структурный узел и выделите ему память.
Добавьте его значение данных как 4
Укажите его следующий указатель на узел структуры, содержащий 2 в качестве значения данных
Измените следующий указатель «1» на только что созданный узел.

Выполнение чего-то подобного в массиве потребовало бы сдвига позиций всех последующих элементов.

В Python и Java связанный список может быть реализован с использованием классов, как показано в кодах ниже.

Утилита связанного списка

Списки - одна из самых популярных и эффективных структур данных, реализуемая на всех языках программирования, таких как C, C ++, Python, Java и C #.

Кроме того, связанные списки - отличный способ узнать, как работают указатели. Практикуясь в работе со связанными списками, вы можете подготовиться к изучению более сложных структур данных, таких как графики и деревья.

Реализации связанных списков в примерах Python, Java, C и C ++

Python Java C C +

 # Linked list implementation in Python class Node: # Creating a node def __init__(self, item): self.item = item self.next = None class LinkedList: def __init__(self): self.head = None if __name__ == '__main__': linked_list = LinkedList() # Assign item values linked_list.head = Node(1) second = Node(2) third = Node(3) # Connect nodes linked_list.head.next = second second.next = third # Print the linked list item while linked_list.head != None: print(linked_list.head.item, end=" ") linked_list.head = linked_list.head.next

 // Linked list implementation in Java class LinkedList ( // Creating a node Node head; static class Node ( int value; Node next; Node(int d) ( value = d; next = null; ) ) public static void main(String() args) ( LinkedList linkedList = new LinkedList(); // Assign value values linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); // Connect nodess linkedList.head.next = second; second.next = third; // printing node-value while (linkedList.head != null) ( System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; ) ) )

 // Linked list implementation in C #include #include // Creating a node struct node ( int value; struct node *next; ); // print the linked list value void printLinkedlist(struct node *p) ( while (p != NULL) ( printf("%d ", p->value); p = p->next; ) ) int main() ( // Initialize nodes struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; // Allocate memory one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // printing node-value head = one; printLinkedlist(head); )

 // Linked list implementation in C++ #include using namespace std; // Creating a node class Node ( public: int value; Node* next; ); int main() ( Node* head; Node* one = NULL; Node* two = NULL; Node* three = NULL; // allocate 3 nodes in the heap one = new Node(); two = new Node(); three = new Node(); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // print the linked list value head = one; while (head != NULL) ( printf("%d ", head->value); head = head->next; ) )