Структура података ЛинкедЛист

У овом упутству ћете научити о структури података повезане листе и њеној примени у Питхон, Јава, Ц и Ц ++.

Структура података повезане листе укључује низ повезаних чворова. Овде сваки чвор чува податке и адресу следећег чвора. На пример,

Структура података ЛинкедЛист

Морате негде започети, па адреси првог чвора додељујемо посебно име под називом ХЕАД.

Такође, последњи чвор на повезаној листи може се идентификовати јер његов следећи део показује на НУЛЛ.

Можда сте играли игру Лов на благо, где сваки траг садржи информације о следећем трагу. Тако функционише повезана листа.

Представљање ЛинкедЛист-а

Погледајмо како је представљен сваки чвор ЛинкедЛист-а. Сваки чвор се састоји од:

  • Ставка података
  • Адреса другог чвора

Ставку података и следећу референцу на чвор умотавамо у структуру као:

 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;

Ако нисте разумели ниједну горњу линију, све што вам треба је освежавање показивача и структура.

У само неколико корака створили смо једноставну повезану листу са три чвора.

Заступљеност на ЛинкедЛист-у

Моћ ЛинкедЛист-а потиче од способности да прекину ланац и поново му се придруже. Нпр. Ако желите да ставите елемент 4 између 1 и 2, кораци би били:

  • Направите нови структурни чвор и доделите му меморију.
  • Додајте вредност података као 4
  • Усмерите његов следећи показивач на структурни чвор који садржи 2 као вредност података
  • Промените следећи показивач „1“ на чвор који смо управо креирали.

Радећи нешто слично у низу захтевало би померање положаја свих наредних елемената.

У питхон-у и Јави, повезана листа се може применити помоћу класа као што је приказано у доњим кодовима.

Услужни програм повезане листе

Листе су једна од најпопуларнијих и најефикаснијих структура података, са применом у свим програмским језицима као што су Ц, Ц ++, Питхон, Јава и Ц #.

Поред тога, повезане листе су одличан начин да научите како показивачи раде. Вежбајући како манипулисати повезаним листама, можете се припремити за учење напреднијих структура података попут графикона и стабала.

Имплементације повезаних листа у примерима Питхон, Јава, Ц и Ц ++

Питхон Јава Ц Ц + 
 # 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; ) )

Сложеност повезане листе

Сложеност времена

Најгори случај Просечан случај
Претрага На) На)
Уметни О (1) О (1)
Делетион О (1) О (1)

Сложеност простора: О (н)

Апликације са повезаним списком

  • Динамичко додељивање меморије
  • Имплементирано у стеку и реду
  • У ундо функционалност софтвера
  • Хасх табеле, графикони

Препоручена читања

1. Туториали

  • Операције ЛинкедЛист (Прелазак, уметање, брисање)
  • Врсте ЛинкедЛист-а
  • Јава ЛинкедЛист

2. Примери

  • Набавите средњи елемент ЛинкедЛист-а у једној итерацији
  • Претворите ЛинкедЛист у низ и обрнуто
  • Откривање петље у ЛинкедЛист-у

Занимљиви Чланци...