Datastrukturer forklaret med eksempler - sammenkædet liste

Ligesom en krans er lavet med blomster, består en sammenkædet liste af noder. Vi kalder hver blomst på denne særlige krans for at være en knude. Og hver af noderne peger på den næste node på denne liste, såvel som den har data (her er det en blomstertype).

Typer

Enkelt forbundet liste

Enkelt forbundne lister indeholder noder, der har et datafelt såvel som et nextfelt, der peger på den næste node i sekvensen. Handlinger, der kan udføres på enkeltkædede lister, er indsættelse, sletning og traversal.

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

Intern implementering af CPython, rammerne og de evaluerede variabler holdes på en stak.

Til dette er vi nødt til kun at gentage fremad for at få hovedet, derfor bruges enkeltkædet-liste.

Dobbelt sammenkædet liste

Dobbelt sammenkædede lister indeholder node, der har datafelt, nextfelt og et andet linkfelt, der prevpeger på den forrige node i sekvensen.

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

Browserens cache, der giver dig mulighed for at trykke på BACK og FORWARD-knappen. Her er vi nødt til at opretholde en dobbeltkoblet liste med URLssom datafelt for at give adgang i begge retninger. For at gå til forrige URL bruger vi prevfelt og for at gå til næste side bruger vi nextfelt.

Cirkulær sammenkædet liste

Cirkelbundne lister er en enkelt linket liste, hvor sidste node, nextfelt peger på første node i sekvensen.

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

Tidsdelingsproblem løst af operativsystemet.

I et timesharing-miljø skal operativsystemet føre en liste over nuværende brugere og skal skiftevis tillade hver bruger at bruge en lille del af CPU-tiden, en bruger ad gangen. Operativsystemet vælger en bruger, lader ham / hende bruge en lille mængde CPU-tid og går derefter videre til den næste bruger.

Til denne applikation skal der ikke være nogen NULL-pegepinde, medmindre der absolut ikke er nogen, der anmoder om CPU-tid, dvs. listen er tom.

Grundlæggende funktioner

Indskud

For at tilføje et nyt element til listen.

Indsættelse i starten:

  • Opret en ny knude med givne data.
  • Ret ny knudepunkt nextmod gammel head.
  • Peg headpå denne nye knude.

Indsættelse i midten / slutningen.

Indsættelse efter node X.

  • Opret en ny knude med givne data.
  • Peg nye knudepunkter nexttil gamle X'er next.
  • Peg X'er nexttil denne nye node.

Tidskompleksitet: O (1)

Sletning

For at slette eksisterende element fra listen.

Sletning i starten

  • Få noden peget headsom Temp.
  • Peg headpå Temp's next.
  • Gratis hukommelse brugt af Temp-node.

Sletning i midten / slutningen.

Sletning efter node X.

  • Få noden peget Xsom Temp.
  • Peg X nexttil Temp next.
  • Gratis hukommelse brugt af Temp-node.

Tidskompleksitet: O (1)

Traversering

At rejse på tværs af listen.

Traversal

  • Få noden peget headsom Strøm.
  • Kontroller, om strømmen ikke er nul, og vis den.
  • Peg strøm til strøm nextog flyt til ovenstående trin.

Tidskompleksitet: O (n) // Her er n størrelsen på linklisten

Implementering

C ++ implementering af enkeltkædet liste

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

Udskrivning af data i hver node

// 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.