Λίστα μεμονωμένα συνδεδεμένα σε δομές δεδομένων

Τι είναι μια μεμονωμένη συνδεδεμένη λίστα;

Η Μονά Συνδεδεμένη Λίστα είναι μια γραμμική και μονοκατευθυντική δομή δεδομένων όπου τα δεδομένα αποθηκεύονται στους κόμβους και κάθε κόμβος συνδέεται μέσω ενός συνδέσμου με τον επόμενο κόμβο του. Κάθε κόμβος περιέχει ένα πεδίο δεδομένων και έναν σύνδεσμο προς τον επόμενο κόμβο. Οι Μονά Συνδεδεμένες Λίστες μπορούν να διασχιστούν μόνο προς μία κατεύθυνση, ενώ μια Διπλή συνδεδεμένη λίστα μπορεί να διασχιστεί και προς τις δύο κατευθύνσεις.

Εδώ είναι η δομή κόμβων μιας Μονά Συνδεδεμένης Λίστας:

Δομή ενός κόμβου σε μια συνδεδεμένη λίστα

Γιατί να χρησιμοποιήσω μια συνδεδεμένη λίστα πάνω από έναν πίνακα;

Αρκετά σενάρια ευνοούν μια συνδεδεμένη λίστα έναντι μιας Παράταξη:

• Άγνωστος αριθμός στοιχείων: Όταν ο απαιτούμενος αριθμός στοιχείων δεν είναι γνωστός κατά το χρόνο μεταγλώττισης, μια συνδεδεμένη λίστα κατανέμει δυναμικά τη μνήμη καθώς προστίθενται στοιχεία.
• Τυχαία πρόσβαση: Όταν δεν απαιτείται τυχαία προσπέλαση με ευρετήριο, μια συνδεδεμένη λίστα είναι μια κατάλληλη επιλογή.
• Εισαγωγή στη μέση: Η εισαγωγή στη μέση ενός πίνακα απαιτεί μετατόπιση στοιχείων. Μια συνδεδεμένη λίστα επιτρέπει την εισαγωγή σε οποιαδήποτε θέση, ξαναγράφοντας μόνο λίγους δείκτες.

Operaθέσεις της Singly Linked List

Μια Μονά Συνδεδεμένη Λίστα είναι καλή για τη δυναμική κατανομή μνήμης. Υποστηρίζει τις τυπικές λειτουργίες της συνδεδεμένης λίστας, δηλαδή εισαγωγή, διαγραφή, αναζήτηση, ενημέρωση, συγχώνευση δύο λιστών και διέλευση.

Οι ακόλουθες λειτουργίες συζητούνται σε αυτό το άρθρο:

• Εισαγωγή στο κεφάλι
• Εισαγωγή στην ουρά
• Εισαγωγή μετά από κόμβο
• Εισαγωγή πριν από έναν κόμβο
• Διαγράψτε τον κόμβο κεφαλής
• Διαγράψτε τον κόμβο της ουράς
• Αναζήτηση και διαγραφή ενός κόμβου
• Διέλευση της συνδεδεμένης λίστας

Ακολουθεί ένα παράδειγμα συνδεδεμένης λίστας με τέσσερις κόμβους.

Παράδειγμα λίστας μεμονωμένα συνδεδεμένα

Εισαγωγή στην αρχή μιας λίστας με μία μόνο σύνδεση

Αυτή είναι μια απλή λειτουργία. Είναι γενικά γνωστή ως προώθηση σε μια λίστα με μία μόνο σύνδεση. Ένας νέος κόμβος δημιουργείται και τοποθετείται στην κορυφή της λίστας.

Για να εκτελέσετε αυτήν την ενέργεια, ακολουθήστε δύο σημαντικές προϋποθέσεις:

1. Εάν η λίστα είναι κενή, ο νεοδημιουργημένος κόμβος γίνεται ο κύριος κόμβος και ο επόμενη Ο δείκτης είναι NULL.
2. Εάν η λίστα δεν είναι κενή, ο νέος κόμβος γίνεται ο κύριος κόμβος και ο επόμενη Ο δείκτης δείχνει στον προηγούμενο κόμβο κεφαλής.

Εδώ είναι ο ψευδοκώδικας για την εισαγωγή ενός κόμβου στην κορυφή μιας συνδεδεμένης λίστας:

function insertAtHead(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  else:
    newNode.next = head
    return newNode

Εισαγωγή στο κεφάλι

Εισαγωγή στο τέλος μιας λίστας με μία μόνο σύνδεση

Η εισαγωγή ενός κόμβου στο τέλος μιας συνδεδεμένης λίστας είναι παρόμοια με την εισαγωγή στην αρχή. Μεταβείτε στον κόμβο της ουράς και, στη συνέχεια, στρέψτε τον προς τα πάνω. επόμενη δείκτης προς τον νέο κόμβο. Εάν η κεφαλή είναι NULL, ο νέος κόμβος γίνεται η κεφαλή.

Βήμα 1) Διασχίστε μέχρι το επόμενη Ο δείκτης του τρέχοντος κόμβου γίνεται NULL.

Βήμα 2) Δημιουργήστε έναν νέο κόμβο με την καθορισμένη τιμή.

Βήμα 3) Αντιστοιχίστε τον νέο κόμβο ως τον επόμενο κόμβο του κόμβου ουράς.

Ο ψευδοκώδικας για την εισαγωγή στην ουρά μιας μεμονωμένης λίστας:

function insertAtEnd(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  while head.next is not NULL:
    head = head.next
  head.next = newNode
  newNode.next = NULL

Εισαγωγή στην ουρά

Εισαγωγή μετά από έναν κόμβο σε μια λίστα με μία μόνο σύνδεση

Η εισαγωγή μετά από έναν κόμβο έχει δύο μέρη: αναζήτηση του κόμβου-στόχου και προσάρτηση ενός νέου κόμβου μετά από αυτόν. Διασχίστε τη λίστα μέχρι να βρεθεί μια αντιστοιχία και, στη συνέχεια, συνδέστε τον νέο κόμβο.

Βήμα 1) Διασχίστε μέχρι η τιμή του τρέχοντος κόμβου να ισούται με το στοιχείο αναζήτησης.

Βήμα 2) Ορίστε τον νέο κόμβο επόμενη δείκτης προς τον τρέχοντα κόμβο επόμενη δείκτης.

Βήμα 3) Στρέψτε τον τρέχοντα κόμβο επόμενη δείκτης προς τον νέο κόμβο.

Ψευδοκώδικας:

function insertAfter(head, value, searchItem):
  newNode = Node(value)
  while head.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Εισαγωγή ενός κόμβου μετά από έναν κόμβο στη λίστα μεμονωμένα συνδεδεμένα

Εισαγωγή πριν από έναν κόμβο σε μια απλά συνδεδεμένη λίστα

Αυτό είναι παρόμοιο με την εισαγωγή μετά από έναν κόμβο. Μετακινηθείτε μέχρι ο επόμενος κόμβος να ταιριάζει με την τιμή αναζήτησης και, στη συνέχεια, εισαγάγετε τον νέο κόμβο πριν από αυτόν.

Βήμα 1) Διασχίστε έως ότου η τιμή του επόμενου κόμβου ισούται με το αντικείμενο αναζήτησης.

Βήμα 2) Δημιουργήστε έναν νέο κόμβο και ορίστε τον επόμενη δείκτης προς τον τρέχοντα κόμβο επόμενη.

Βήμα 3) Στρέψτε τον τρέχοντα κόμβο επόμενη στον νέο κόμβο.

function insertBefore(head, value, searchItem):
  newNode = Node(value)
  while head.next.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Εισαγωγή ενός κόμβου πριν από έναν κόμβο στη λίστα μεμονωμένα συνδεδεμένα

Διαγραφή της κεφαλής της λίστας με μία μόνο σύνδεση

Ο δείκτης κεφαλής παρέχεται ως παράμετρος. Ο κόμβος κεφαλής αφαιρείται και ο επόμενος κόμβος γίνεται ο νέος κόμβος. Η μνήμη του διαγραμμένου κόμβου πρέπει να απελευθερωθεί για να αποφευχθούν διαρροές μνήμης.

Βήμα 1) Αντιστοιχίστε τον επόμενο κόμβο της κεφαλής ως τη νέα κεφαλή.

Βήμα 2) Απελευθερώστε την εκχωρημένη μνήμη του προηγούμενου κόμβου κεφαλής.

Βήμα 3) Επιστρέψτε τον νέο κόμβο κεφαλής.

function deleteHead(head):
  temp = head
  head = head.next
  free(temp)
  return head

Διαγραφή της κεφαλής μιας συνδεδεμένης λίστας

Διαγραφή της ουράς της λίστας με μοναδική σύνδεση

Η διαγραφή του ουραίου κόμβου είναι παρόμοια με τη διαγραφή του κύριου κόμβου. Η διαφορά είναι ότι απαιτείται η μετάβαση στο τέλος της λίστας. Σε μια Μονά Συνδεδεμένη Λίστα, ο κόμβος του οποίου επόμενη Ο δείκτης είναι NULL και είναι ο κόμβος της ουράς.

Βήμα 1) Διασχίστε μέχρι ακριβώς πριν από τον κόμβο της ουράς. Αποθηκεύστε τον τρέχοντα κόμβο.

Βήμα 2) Απελευθερώστε τη μνήμη του επόμενου κόμβου (της ουράς).

Βήμα 3) Ορίστε τον επόμενο κόμβο του τρέχοντος κόμβου σε NULL.

function deleteTail(head):
  while head.next.next is not NULL:
    head = head.next
  free(head.next)
  head.next = NULL

Διαγραφή της ουράς της Singly Linked List

Αναζήτηση και διαγραφή κόμβου από μια λίστα μεμονωμένων συνδέσεων

Αυτή η συνάρτηση εκτελεί δύο εργασίες: αναζήτηση και διαγραφή. Μετακινηθείτε μέχρι το τέλος της λίστας. Εάν βρεθεί ένας αντίστοιχος κόμβος, αφαιρέστε τον και επανασυνδέστε τον προηγούμενο κόμβο. επόμενη δείκτης.

Βήμα 1) Μετακινηθείτε μέχρι το τέλος της λίστας. Ελέγξτε αν ο τρέχων κόμβος είναι ίσος με τον κόμβο αναζήτησης.

Βήμα 2) Εάν βρεθεί κάποια αντιστοιχία, αποθηκεύστε έναν δείκτη στον τρέχοντα κόμβο.

Βήμα 3) The επόμενη του προηγούμενου κόμβου γίνεται ο επόμενος κόμβος του τρέχοντος κόμβου.

Βήμα 4) Διαγράψτε τον τρέχοντα κόμβο και ελευθερώστε τη μνήμη του.

function searchAndDelete(head, searchItem):
  while head.next.next is not NULL and head.next.value != searchItem:
    head = head.next
  temp = head.next
  head.next = head.next.next
  free(temp)

Αναζητήστε και διαγράψτε έναν κόμβο από τη λίστα μεμονωμένα συνδεδεμένα

Διασχίστε μια λίστα με μία μόνο σύνδεση

Μια λίστα με μία μόνο σύνδεση υποστηρίζει μόνο τη διέλευση από την αρχή έως το τέλος. Δεν υπάρχει δείκτης προς τον προηγούμενο κόμβο, επομένως η αντίστροφη διέλευση δεν είναι δυνατή. Κάθε κόμβος επισκέπτεται με τη σειρά του, εκτυπώνοντας την τιμή του μέχρι να επιτευχθεί η τιμή NULL.

Βήμα 1) Διασχίστε κάθε κόμβο μέχρι να επιτευχθεί η τιμή NULL.

Βήμα 2) Εκτυπώστε την τιμή του τρέχοντος κόμβου.

function traverse(head):
  while head is not NULL:
    print head.value
    head = head.next

Παράδειγμα μεμονωμένα συνδεδεμένης λίστας σε C++

#include<iostream>
using namespace std;
struct Node{
  int data;
  struct Node *next;
};
void insertAtHead(Node* &head, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  if(head != NULL){
    newNode->next = head;
  }
  head = newNode;
  cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
  if(head == NULL){
    insertAtHead(head, value);
    return;
  }
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *temp = head;
  while(temp->next != NULL){
    temp = temp->next;
  }
  temp->next = newNode;
  cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
  Node *temp = NULL;
  if((*headPtr)->data == searchItem){
    temp = *headPtr;
    *headPtr = (*headPtr)->next;
    free(temp);
  } else {
    Node *currentNode = *headPtr;
    while(currentNode->next != NULL){
      if(currentNode->next->data == searchItem){
        temp = currentNode->next;
        currentNode->next = currentNode->next->next;
        free(temp);
        break;
      } else {
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
void insertAfter(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->next->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){
  Node* tempNode = headPointer;
  cout<<"Traversal from head:\t";
  while(tempNode != NULL){
    cout<<tempNode->data;
    if(tempNode->next)
      cout<<" --> ";
    tempNode = tempNode->next;
  }
  cout<<endl;
}
int main(){
  Node *head = NULL;
  insertAtHead(head, 5);
  insertAtHead(head, 6);
  insertAtHead(head, 7);
  insertEnd(head, 9);
  traverse(head);
  searchAndDelete(&head, 6);
  traverse(head);
  insertAfter(head, 7, 10);
  insertBefore(head, 9, 11);
  traverse(head);
}

Παραγωγή

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Traversal from head:    7 --> 6 --> 5 --> 9
Deleted Node    6
Traversal from head:    7 --> 5 --> 9
Inserted 10 after node  7
Inserted 11 before node 9
Traversal from head:    7 --> 10 --> 5 --> 11 --> 9

Παράδειγμα μεμονωμένα συνδεδεμένης λίστας σε Python

class Node:
  def __init__(self, data=None, next=None):
    self.data = data
    self.next = next
class SinglyLinkedList:
  def __init__(self):
    self.head = None
  def insertAtHead(self, value):
    newNode = Node(data=value)
    if self.head is not None:
      newNode.next = self.head
    self.head = newNode
    print(f'Added {newNode.data} at the front.')
  def insertAtEnd(self, value):
    if self.head is None:
      self.insertAtHead(value)
      return
    newNode = Node(value)
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    print(f'Added {newNode.data} at the end.')
  def searchAndDelete(self, searchItem):
    if self.head is None:
      return
    if self.head.data == searchItem:
      self.head = self.head.next
      print(f'Deleted node\t{searchItem}')
      return
    currentNode = self.head
    while currentNode.next is not None:
      if currentNode.next.data == searchItem:
        currentNode.next = currentNode.next.next
        print(f'Deleted node\t{searchItem}')
        return
      currentNode = currentNode.next
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
  def traverse(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
singlyLinkedList = SinglyLinkedList()
singlyLinkedList.insertAtHead(5)
singlyLinkedList.insertAtHead(6)
singlyLinkedList.insertAtHead(7)
singlyLinkedList.insertAtEnd(9)
singlyLinkedList.traverse()
singlyLinkedList.searchAndDelete(6)
singlyLinkedList.traverse()
singlyLinkedList.insertAfter(7, 10)
singlyLinkedList.insertBefore(9, 11)
singlyLinkedList.traverse()

Παραγωγή

Added 5 at the front.
Added 6 at the front.
Added 7 at the front.
Added 9 at the end.
Traversing from head:   7       6       5       9
Deleted node    6
Traversing from head:   7       5       9
Inserted 10 after node  7
Inserted 11 before node 9
Traversing from head:   7       10      5       11      9

Πολυπλοκότητα της λίστας μεμονωμένα συνδεδεμένα

Υπάρχουν δύο είδη πολυπλοκότητας: η χρονική πολυπλοκότητα και η χωρική πολυπλοκότητα. Η χειρότερη και η μέση χρονική πολυπλοκότητα είναι οι ίδιες για μια Μονά Συνδεδεμένη Λίστα.

καλυτερα-case time complexity:

• Η εισαγωγή στην αρχή μπορεί να γίνει στο O(1). Δεν απαιτείται διέλευση μέσα στη λίστα.
• Η αναζήτηση και η διαγραφή μπορούν να γίνουν στο O(1) εάν το στοιχείο-στόχος βρίσκεται στον κύριο κόμβο.

Μέση χρονική πολυπλοκότητα υπόθεσης:

• Η εισαγωγή μέσα σε μια συνδεδεμένη λίστα παίρνει O(n), όπου n είναι ο συνολικός αριθμός των στοιχείων.
• Η αναζήτηση και η διαγραφή μπορούν επίσης να λάβουν O(n), επειδή το στοιχείο-στόχος μπορεί να βρίσκεται οπουδήποτε μέχρι τον κόμβο tail.

Πολυπλοκότητα χώρου μιας μονοσυνδεδεμένης λίστας

Μια Μονά Συνδεδεμένη Λίστα κατανέμει δυναμικά μνήμη. Για αποθήκευση n στοιχεία, κατανέμει n μονάδες μνήμης. Έτσι, η πολυπλοκότητα του χώρου είναι O(n).

Εφαρμογές Μονά Συνδεδεμένης Λίστας

Οι μονά συνδεδεμένες λίστες εμφανίζονται σε πολλά σημεία όπου η διέλευση μόνο προς τα εμπρός και η δυναμική μνήμη είναι χρήσιμες:

• Στοίβες και ουρές: Υποκείμενος χώρος αποθήκευσης για στοίβες LIFO και ουρές FIFO που δημιουργούνται από κόμβους.
• Αλυσιδωτή σύνδεση πίνακα κατακερματισμού: Οι συγκρούσεις επιλύονται με την αλυσιδωτή σύνδεση καταχωρήσεων σε μια Μονά Συνδεδεμένη Λίστα ανά κάδο.
• Λίστες γειτνίασης: Τα αραιά γραφήματα χρησιμοποιούν μια Μονά Συνδεδεμένη Λίστα γειτόνων για κάθε κορυφή.
• Πίνακες συμβόλων: Οι μεταγλωττιστές και οι διερμηνείς συνδέουν τα αναγνωριστικά σε μια λίστα με μία μόνο σύνδεση ανά πεδίο εφαρμογής.
• Κατανεμητές μνήμης: Ελεύθεροι κατανεμητές λίστας track ελεύθερα μπλοκ ως Μονά Συνδεδεμένη Λίστα.

Συχνές Ερωτήσεις