LinkedList datu struktūra

Šajā apmācībā jūs uzzināsiet par saistītā saraksta datu struktūru un tās ieviešanu Python, Java, C un C ++.

Saistītā saraksta datu struktūra ietver virkni savienotu mezglu. Šeit katrs mezgls saglabā datus un nākamā mezgla adresi. Piemēram,

LinkedList datu struktūra

Jums jāsāk kaut kur, tāpēc mēs piešķiram pirmā mezgla adresei īpašu nosaukumu ar nosaukumu HEAD.

Arī pēdējo saistītā saraksta mezglu var noteikt, jo tā nākamā daļa norāda uz NULL.

Iespējams, ka esat spēlējis spēli Dārgumu medības, kur katrs pavediens satur informāciju par nākamo pavedienu. Tā darbojas sasaistītais saraksts.

LinkedList attēlojums

Apskatīsim, kā tiek attēlots katrs LinkedList mezgls. Katrs mezgls sastāv no:

  • Datu vienums
  • Cita mezgla adrese

Mēs aptinam gan datu vienumu, gan nākamo mezgla atsauci struktūrā kā:

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

Saistītā saraksta mezgla struktūras izpratne ir atslēga, lai to saprastu.

Katrā struktūras mezglā ir datu vienums un norāde uz citu struktūras mezglu. Izveidosim vienkāršu saistīto sarakstu ar trim vienumiem, lai saprastu, kā tas darbojas.

 /* 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;

Ja jūs nesapratāt nevienu no iepriekšminētajām līnijām, viss, kas jums nepieciešams, ir atsvaidzināt rādītājus un struktūras.

Veicot tikai dažas darbības, mēs esam izveidojuši vienkāršu saistīto sarakstu ar trim mezgliem.

LinkedList pārstāvniecība

LinkedList spēks rodas no spējas pārtraukt ķēdi un atkal pievienoties tai. Piemēram, ja vēlaties ievietot elementu 4 starp 1 un 2, soļi būtu šādi:

  • Izveidojiet jaunu struktūras mezglu un piešķiriet tam atmiņu.
  • Pievienojiet tā datu vērtību kā 4
  • Novietojiet nākamo rādītāju uz struktūras mezglu, kurā datu vērtība ir 2
  • Mainiet nākamo rādītāju "1" uz tikko izveidoto mezglu.

Veicot kaut ko līdzīgu masīvā, būtu jāmaina visu nākamo elementu pozīcijas.

Pitonā un Java saistīto sarakstu var ieviest, izmantojot klases, kā parādīts zemāk esošajos kodos.

Saistītā saraksta utilīta

Saraksti ir viena no populārākajām un efektīvākajām datu struktūrām, kas tiek ieviesta visās programmēšanas valodās, piemēram, C, C ++, Python, Java un C #.

Bez tam saistītie saraksti ir lielisks veids, kā uzzināt, kā rādītāji darbojas. Praktizējot, kā manipulēt ar saistītajiem sarakstiem, jūs varat sagatavoties, lai uzzinātu uzlabotas datu struktūras, piemēram, diagrammas un kokus.

Saistīto sarakstu ieviešana Python, Java, C un C ++ piemēros

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; ) )

Saistītā saraksta sarežģītība

Laika sarežģītība

Sliktākajā gadījumā Vidējais gadījums
Meklēt O (n) O (n)
Ievietojiet O (1) O (1)
Dzēšana O (1) O (1)

Kosmosa sarežģītība: O (n)

Saistītā saraksta lietojumprogrammas

  • Dinamiska atmiņas piešķiršana
  • Ievietots kaudzē un rindā
  • Programmatūras atsaukšanas funkcijās
  • Hash tabulas, grafiki

Ieteicamie lasījumi

1. Apmācības

  • LinkedList darbības (pārvietošanās, ievietošana, dzēšana)
  • LinkedList veidi
  • Java LinkedList

2. Piemēri

  • Iegūstiet LinkedList vidējo elementu vienā atkārtojumā
  • Pārveidojiet LinkedList par masīvu un otrādi
  • Noteikt cilpu LinkedList

Interesanti raksti...