Näidetega selgitatud andmestruktuurid - lingitud loend

Nii nagu lillepärg on tehtud, koosneb ka linkide loend sõlmedest. Kutsume kõiki selle konkreetse pärja lilli sõlmpunktiks. Ja iga sõlm osutab selles loendis järgmisele sõlmele, samuti on sellel andmeid (siin on see lille tüüp).

Tüübid

Üksikult lingitud loend

Üksikult lingitud loendid sisaldavad sõlme, millel on nii dataväli kui ka nextväli, mis osutab järjestuse järgmisele sõlmele. Toimingud, mida saab teha eraldi lingitud loendites, on sisestamine, kustutamine ja läbimine.

 head | | +-----+--+ +-----+--+ +-----+------+ | 1 |o-----> | 2 |o-----> | 3 | NULL | +-----+--+ +-----+--+ +-----+------+

CPythoni sisemine juurutamine, raamid ja hinnatud muutujad hoitakse virnas.

Selleks peame kordama ainult päikest edasi, seetõttu kasutatakse üksikult lingitud loendit.

Kahekordse lingiga loend

Kahekordse lingiga loendid sisaldavad sõlme, millel on dataväli, nextväli ja teine lingiväli, mis prevosutab järjestuse eelmisele sõlmele.

 head | | +------+-----+--+ +--+-----+--+ +-----+------+ | | |o------> | |o------> | | | | NULL | 1 | | 2 | | 3 | NULL | | | | <------o| | <------o| | | +------+-----+--+ +--+-----+--+ +-----+------+

Brauseri vahemälu, mis võimaldab teil vajutada nuppu TAGASI ja EDASI. Siin peame pidama topeltlingitud loendit URLsandmeväljana, et võimaldada juurdepääsu mõlemas suunas. Eelmisele URL-ile liikumiseks kasutame prevvälja ja järgmisele lehele liikumiseks nextvälja.

Ringkirjaga seotud loend

Ringikujulised loendid on üksikult lingitud loend, milles viimane nextväli osutab jada esimesele sõlmele.

 head | | +-----+--+ +-----+--+ +-----+--+ —> | 1 |o-----> | 2 |o-----> | 3 |o----| +-----+--+ +-----+--+ +-----+--+

Aja jagamise probleem on operatsioonisüsteemi abil lahendatud.

Osaajaja keskkonnas peab operatsioonisüsteem pidama olemasolevate kasutajate loendit ja lubama vaheldumisi igal kasutajal kasutada väikest osa protsessori ajast, üks kasutaja korraga. Operatsioonisüsteem valib kasutaja, laseb tal kasutada väikest osa protsessori ajast ja seejärel järgmise kasutaja juurde.

Selle rakenduse jaoks ei tohiks olla NULL-i osutajaid, kui pole kedagi, kes taotleks protsessori aega, st loend on tühi.

Põhitoimingud

Sisestamine

Uue elemendi lisamine loendisse.

Lisamine algusesse:

  • Looge uus sõlm antud andmetega.
  • Suunake uus sõlm nextvanale head.
  • Osutage headsellele uuele sõlmele.

Sisestamine keskele / otsa.

Lisamine pärast sõlme X.

  • Looge uus sõlm antud andmetega.
  • Suunake uued sõlmed nextvanadele X-idele next.
  • nextSelle uue sõlme punkt X.

Aja keerukus: O (1)

Kustutamine

Olemasoleva elemendi loendist kustutamine.

Kustutamine alguses

  • Hangi sõlm tähistatud headkui Temp.
  • Osutage headTemp's next.
  • Vaba mälu, mida kasutab sõlm Temp.

Kustutamine keskel / lõpus.

Kustutamine sõlme X järel.

  • Hangi sõlm tähistatud Xkui Temp.
  • Punkt X nexttähistab Tempsi next.
  • Vaba mälu, mida kasutab sõlm Temp.

Aja keerukus: O (1)

Läbivad

Nimekirja kaudu reisimiseks.

Läbimine

  • Hangi sõlm headtähistatud praegusega.
  • Kontrollige, kas Current pole null, ja kuvage see.
  • Suunake praegune voolu suunas nextja liikuge ülemisele sammule.

Aja keerukus: O (n) // Siin n on linkide loendi suurus

Rakendamine

Ainult lingitud loendi C ++ rakendamine

// Header files #include  struct node { int data; struct node *next; }; // Head pointer always points to first element of the linked list struct node *head = NULL;

Andmete printimine igasse sõlme

// Display the list void printList() { struct node *ptr = head; // Start from the beginning while(ptr != NULL) { std::cout 

Insertion at the beginning

// Insert link at the beginning void insertFirst(int data) { // Create a new node struct node *new_node = new struct node; new_node->data = data; // Point it to old head new_node->next = head; // Point head to new node head = new_node; std::cout << "Inserted successfully" << std::endl; }

Deletion at the beginning

// Delete first item void deleteFirst() { // Save reference to head struct node *temp = head; // Point head to head's next head = head->next; // Free memory used by temp temp = NULL: delete temp; std::cout << "Deleted successfully" << std::endl; }

Size

// Find no. of nodes in link list void size() { int length = 0; struct node *current; for(current = head; current != NULL; current = current->next) { length++; } std::cout << "Size of Linked List is " << length << std::endl; }

Searching

// Find node with given data void find(int data){ // Start from the head struct node* current = head; // If list is empty if(head == NULL) { std::cout << "List is empty" next == NULL){ std::cout << "Not Found" 
      

Deletion after a node

// Delete a node with given data void del(int data){ // Start from the first node struct node* current = head; struct node* previous = NULL; // If list is empty if(head == NULL){ std::cout << "List is empty" next == NULL){ std::cout << "Element not found" 
       
        next; } else { // Skip the current node previous->next = current->next; } // Free space used by deleted node current = NULL; delete current; std::cout << "Deleted succesfully" << std::endl; }
       

Python Implementation of Singly Linked List

class Node(object): # Constructor def __init__(self, data=None, next=None): self.data = data self.next = next # Function to get data def get_data(self): return self.data # Function to get next node def get_next(self): return self.next # Function to set next field def set_next(self, new_next): self.next = new_next class LinkedList(object): def __init__(self, head=None): self.head = head

Insertion

 # Function to insert data def insert(self, data): # new_node is a object of class Node new_node = Node(data) new_node.set_next(self.head) self.head = new_node print("Node with data " + str(data) + " is created succesfully")

Size

 # Function to get size def size(self): current = self.head count = 0 while current: count += 1 current = current.get_next() print("Size of link list is " + str(count))

Searching

 # Function to search a data def search(self, data): current = self.head found = False while current and found is False: if current.get_data() == data: found = True else: current = current.get_next() if current is None: print("Node with data " + str(data) + " is not present") else: print("Node with data " + str(data) + " is found")

Deletion after a node

 # Function to delete a node with data def delete(self, data): current = self.head previous = None found = False while current and found is False: if current.get_data() == data: found = True else: previous = current current = current.get_next() if current is None: print("Node with data " + str(data) + " is not in list") elif previous is None: self.head = current.get_next() print("Node with data " + str(data) + " is deleted successfully") else: previous.set_next(current.get_next()) print("Node with data " + str(data) + " is deleted successfully")

Advantages

  1. Linked lists are a dynamic data structure, which can grow and shrink, allocating and deallocating memory while the program is running.
  2. Insertion and deletion of node are easily implemented in a linked list at any position.

Disadvantages

  1. They use more memory than arrays because of the memory used by their pointers (next and prev).
  2. Random access is not possible in linked list. We have to access nodes sequentially.
  3. It’s more complex than array. If a language supports array bound check automatically, Arrays would serve you better.

Note

We have to use free() in C and delete in C++ to free the space used by deleted node, whereas, in Python and Java free space is collected automatically by garbage collector.