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

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

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

Ακολουθεί μια δομή κόμβου μιας λίστας μεμονωμένα συνδεδεμένα:

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

Υπάρχουν αρκετές περιπτώσεις κατά τις οποίες είναι καλύτερο να χρησιμοποιήσετε τη Συνδεδεμένη Λίστα αντί της Παράταξη. Ορίστε μερικά σενάρια:

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

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

Η 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

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

Η εισαγωγή ενός κόμβου στο τέλος μιας συνδεδεμένης λίστας έχει κάποιες ομοιότητες με την εισαγωγή στην κεφαλή. Το μόνο που χρειάζεται να κάνετε είναι να διασχίσετε τον ακραίο κόμβο ή τον κόμβο της ουράς. Στη συνέχεια, τοποθετήστε τον «επόμενο» κόμβο του τερματικού κόμβου στον κόμβο που δημιουργήθηκε πρόσφατα. Εάν ο κύριος κόμβος είναι μηδενικός, ο νέος κόμβος θα είναι ο κύριος κόμβος.

Εδώ είναι τα βήματα:

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

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

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

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

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

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

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

Εδώ είναι τα βήματα:

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

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

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

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

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

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

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

Εδώ είναι τα βήματα:

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

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

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

Εδώ είναι ο ψευδοκώδικας:

function insertBefore( head, value, searchItem ):
	newNode = Node(value)
	while head.next.value equals searchItem:
		then head = head.next
	newNode.next = head.next.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

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

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

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

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

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

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

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

function searchAndDelete( head, searchItem ):
	while head.next.next is not NULL  and head.next.value is not equals searchItem :
		head = head.next
	head.next = head.next.next
	delete(head.next)

Διασχίστε μια λίστα μεμονωμένα συνδεδεμένα

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

Εδώ είναι τα βήματα:

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

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

Ψευδο-κωδικός για τη διέλευση μιας λίστας μεμονωμένα συνδεδεμένα:

function traverse( head ):
		while head.next is not NULL:
			print the value of the head
			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);
  }
  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 = new Node();
  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);
      }else{
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
}
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 = new 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.')
    return  
  def insertAtEnd(self,value):
    if self.head is None:
      self.insertAtHead(value)
    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):
    temp = Node()
    if self.head is searchItem:
      temp = self.head
      self.head = self.head.next
    else:
      currentNode = self.head
      while currentNode.next is not None:
        if currentNode.next.data is searchItem:
          temp = currentNode.next
          currentNode.next = currentNode.next.next
        else:
          currentNode = currentNode.next
    print(f'Deleted node\t{searchItem}')
    return
  def insertAfter(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
    return 
  def insertbefore(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
    return
  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

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

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

Η χρονική πολυπλοκότητα για την καλύτερη περίπτωση:

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

Η χρονική πολυπλοκότητα για τη μέση περίπτωση:

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

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

Η Singly Linked List εκχωρεί δυναμικά τη μνήμη. Αν θέλουμε να αποθηκεύσουμε n στοιχεία, θα διαθέσει n μονάδα μνήμης. Άρα, η πολυπλοκότητα του χώρου είναι O(n).