Šioje pamokoje sužinosite apie susieto sąrašo duomenų struktūrą ir jos įgyvendinimą „Python“, „Java“, „C“ ir „C ++“.
Susieto sąrašo duomenų struktūra apima sujungtų mazgų seriją. Čia kiekvienas mazgas saugo kito mazgo duomenis ir adresą. Pavyzdžiui,
„LinkedList“ duomenų struktūra
Jūs turite pradėti nuo kažkur, todėl pirmojo mazgo adresui suteikiame specialų pavadinimą, vadinamą GALVA.
Be to, paskutinį susieto sąrašo mazgą galima nustatyti, nes jo kita dalis nukreipta į NULL.
Galbūt žaidėte žaidimą „Lobių ieškojimas“, kur kiekviename užuominoje pateikiama informacija apie kitą užuominą. Taip veikia susietas sąrašas.
„LinkedList“ atstovavimas
Pažiūrėkime, kaip pavaizduotas kiekvienas „LinkedList“ mazgas. Kiekvieną mazgą sudaro:
- Duomenų elementas
- Kito mazgo adresas
Duomenų elementą ir kitą mazgo nuorodą įvyniojame į struktūrą kaip:
struct node ( int data; struct node *next; );
Suprasti susieto sąrašo mazgo struktūrą yra raktas į jo suvokimą.
Kiekviename struktūros mazge yra duomenų elementas ir žymeklis į kitą struktūros mazgą. Sukurkime paprastą susietų sąrašą su trimis elementais, kad suprastume, kaip tai veikia.
/* 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;
Jei nesupratote nė vienos iš anksčiau pateiktų eilučių, jums tereikia atnaujinti rodykles ir nurodymus.
Vos atlikdami kelis veiksmus, mes sukūrėme paprastą susietą sąrašą su trimis mazgais.
„LinkedList“ atstovavimas
„LinkedList“ galia kyla iš sugebėjimo nutraukti grandinę ir prisijungti prie jos. Pvz., Jei norėtumėte įdėti elementą 4 tarp 1 ir 2, bus atlikti šie veiksmai:
- Sukurkite naują struktūros mazgą ir paskirstykite jam atmintį.
- Pridėkite jo duomenų vertę kaip 4
- Nukreipkite kitą rodyklę į struktūros mazgą, kuriame duomenų reikšmė yra 2
- Pakeiskite kitą rodyklę „1“ į ką tik sukurtą mazgą.
Norint padaryti kažką panašaus masyve, reikėjo pakeisti visų tolesnių elementų pozicijas.
„Python“ ir „Java“ susietą sąrašą galima įgyvendinti naudojant klases, kaip parodyta žemiau esančiuose koduose.
Susietų sąrašų įrankis
Sąrašai yra viena iš populiariausių ir efektyviausių duomenų struktūrų, įdiegta visomis programavimo kalbomis, tokiomis kaip C, C ++, Python, Java ir C #.
Be to, susieti sąrašai yra puikus būdas sužinoti, kaip veikia rodyklės. Praktikuodamiesi, kaip tvarkyti susietus sąrašus, galite pasiruošti mokytis pažangesnių duomenų struktūrų, pvz., Grafikų ir medžių.
Susietų sąrašų diegimas „Python“, „Java“, C ir C ++ pavyzdžiuose
„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; ) )
Susieto sąrašo sudėtingumas
Laiko kompleksiškumas
| Blogiausiu atveju | Vidutinis atvejis | |
|---|---|---|
| Paieška | O (n) | O (n) |
| Įdėti | O (1) | O (1) |
| Ištrinti | O (1) | O (1) |
Erdvės sudėtingumas: O (n)
Susietų programų programos
- Dinaminis atminties paskirstymas
- Įdiegta kamino ir eilės
- Į anuliuoti funkcionalumo programinės įrangos
- Maišos lentelės, grafikai
Rekomenduojami skaitiniai
1. Pamokos
- „LinkedList“ operacijos (perėjimas, įterpimas, ištrynimas)
- „LinkedList“ tipai
- „Java LinkedList“
2. Pavyzdžiai
- Gaukite vidurinį „LinkedList“ elementą vienoje iteracijoje
- Konvertuokite „LinkedList“ į masyvą ir atvirkščiai
- Aptikti kilpą „LinkedList“
