Strukture podataka objašnjene primjerima - povezani popis

Baš kao što se vijenac izrađuje od cvijeća, povezani popis čine čvorovi. Svaki cvijet na ovom vijencu nazivamo čvorom. I svaki čvor pokazuje na sljedeći čvor na ovom popisu, kao i da ima podatke (ovdje je to vrsta cvijeta).

Vrste

Popis pojedinačno povezanih

Pojedinačno povezani popisi sadrže čvorove koji imaju datapolje, kao i nextpolje koje upućuje na sljedeći čvor u nizu. Operacije koje se mogu izvoditi na pojedinačno povezanim popisima su umetanje, brisanje i obrtanje.

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

Interna implementacija CPythona, okviri i procijenjene varijable čuvaju se na stogu.

Za to trebamo ponoviti samo naprijed aur da dobijemo glavu, stoga se koristi pojedinačno povezani popis.

Popis dvostruko povezanih

Dvostruko povezani popisi sadrže čvor koji ima datapolje, nextpolje i drugo polje veze koje prevupućuju na prethodni čvor u nizu.

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

Predmemorija preglednika koja vam omogućuje da pritisnete tipku NAZAD i NAPRIJED. Ovdje trebamo održavati dvostruko povezan popis, URLskao polje podataka, kako bi se omogućio pristup u oba smjera. Za prelazak na prethodni URL koristit ćemo prevpolje, a za prelazak na sljedeću stranicu next.

Kružno povezani popis

Kružno povezani popisi su pojedinačno povezani popisi u kojima zadnji čvor, nextpolje pokazuje na prvi čvor u nizu.

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

Problem dijeljenja vremena riješen operativnim sustavom.

U okruženju dijeljenja vremena, operativni sustav mora održavati popis prisutnih korisnika i mora naizmjence dopustiti svakom korisniku da koristi mali dio CPU vremena, jednog po jednog korisnika. Operativni sustav odabrat će korisnika, dopustiti mu da iskoristi malu količinu procesorskog vremena, a zatim prijeći na sljedećeg korisnika.

Za ovu aplikaciju ne bi trebalo biti NULL pokazivača, osim ako apsolutno nitko ne traži CPU vrijeme, tj. Popis je prazan.

Osnovne operacije

Umetanje

Da biste dodali novi element na popis.

Umetanje na početku:

  • Stvorite novi čvor s danim podacima.
  • Usmjerite novi čvor nextna stari head.
  • Pokažite headna ovaj novi čvor.

Umetanje u sredinu / kraj.

Umetanje nakon čvora X.

  • Stvorite novi čvor s danim podacima.
  • Točka novi čvor je nextda stari x-a next.
  • Usmjerite X nextdo ovog novog čvora.

Složenost vremena: O (1)

Brisanje

Da biste izbrisali postojeći element sa popisa.

Brisanje na početku

  • Dobijte čvor označen headkao Temp.
  • Pokažite headna Temp next.
  • Slobodna memorija koju koristi čvor Temp.

Brisanje na sredini / kraju.

Brisanje nakon čvora X.

  • Dobijte čvor označen Xkao Temp.
  • Točka X nextprema Temp next.
  • Slobodna memorija koju koristi čvor Temp.

Složenost vremena: O (1)

Prelazak

Putovati preko popisa.

Preokret

  • Dobijte čvor usmjeren headkao Current.
  • Provjerite je li Current nije null i prikažite ga.
  • Usmjerite struju na struju nexti pomaknite se na gornji korak.

Složenost vremena: O (n) // Ovdje je n veličina popisa veza

Provedba

C ++ implementacija pojedinačno povezanog popisa

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

Ispis podataka u svakom čvoru

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