data-structures => Verknüpfte Liste

Einführung in verknüpfte Listen

Eine verknüpfte Liste ist eine lineare Sammlung von Datenelementen, die als Knoten bezeichnet werden, die über einen "Zeiger" mit anderen Knoten verbunden sind. Nachfolgend finden Sie eine einzeln verknüpfte Liste mit einer Kopfreferenz.

         ┌─────────┬─────────┐   ┌─────────┬─────────┐         
 HEAD ──▶│  data   │"pointer"│──▶│  data   │"pointer"│──▶ null 
         └─────────┴─────────┘   └─────────┴─────────┘

Es gibt viele Arten von verknüpften Listen, darunter einfach und doppelt verknüpfte Listen und zirkuläre verknüpfte Listen.

Vorteile

Verknüpfte Listen sind eine dynamische Datenstruktur, die vergrößert und verkleinert werden kann, wobei während der Ausführung des Programms Speicher zugewiesen und freigegeben wird.
Knoteneinfügungs- und Löschvorgänge lassen sich leicht in einer verknüpften Liste implementieren.
Lineare Datenstrukturen wie Stapel und Warteschlangen lassen sich leicht mit einer verketteten Liste implementieren.
Verknüpfte Listen können die Zugriffszeit reduzieren und können in Echtzeit ohne Speicheraufwand erweitert werden.

Einfach verknüpfte Liste

Einfach verknüpfte Listen sind eine Art verknüpfter Liste . Die Knoten einer einzeln verknüpften Liste haben nur einen "Zeiger" auf einen anderen Knoten, normalerweise "Nächster". Sie wird als einzeln verknüpfte Liste bezeichnet, da jeder Knoten nur einen einzelnen "Zeiger" auf einen anderen Knoten hat. Eine einfach verknüpfte Liste kann eine Kopf- und / oder Schwanzreferenz haben. Der Vorteil einer Tail-Referenz sind die getFromBack , addToBack und removeFromBack , die zu O (1) werden.

         ┌─────────┬─────────┐   ┌─────────┬─────────┐         
 HEAD ──▶│  data   │"pointer"│──▶│  data   │"pointer"│──▶ null 
         └─────────┴────△────┘   └─────────┴─────────┘         
          SINGLE        │                                      
          REFERENCE ────┘

Beispielcode in C

Beispielcode in Java mit Komponententests - Einfach verknüpfte Liste mit Kopfreferenz

XOR-verknüpfte Liste

Eine XOR-verknüpfte Liste wird auch als speichereffiziente verknüpfte Liste bezeichnet . Es ist eine andere Form einer doppelt verknüpften Liste. Dies hängt stark von dem XOR- Logikgatter und seinen Eigenschaften ab.

Warum wird dies als speichereffiziente verknüpfte Liste bezeichnet?

Dies wird so genannt, weil dies weniger Speicher benötigt als eine herkömmliche doppelt verknüpfte Liste.

Unterscheidet sich dies von einer doppelt verknüpften Liste?

Ja das ist es.

Eine doppelt verknüpfte Liste speichert zwei Zeiger, die auf den nächsten und den vorherigen Knoten zeigen. Wenn Sie zurückgehen möchten, gehen Sie grundsätzlich zu der Adresse, auf die der back Zeiger zeigt. Wenn Sie vorwärts gehen möchten, gehen Sie zu der Adresse, auf die der next Zeiger zeigt. Es ist wie:

Eine speichereffiziente verknüpfte Liste oder nämlich die verknüpfte XOR-Liste hat nur einen Zeiger anstelle von zwei. Dies speichert die vorherige Adresse (addr (prev)), XOR (^) die nächste Adresse (addr (next)). Wenn Sie zum nächsten Knoten wechseln möchten, führen Sie bestimmte Berechnungen durch und ermitteln die Adresse des nächsten Knotens. Dies ist das Gleiche, wenn Sie zum vorherigen Knoten gehen. Es ist wie:

Wie funktioniert es?

Um zu verstehen, wie die verknüpfte Liste funktioniert, müssen Sie die Eigenschaften von XOR (^) kennen:

|-------------|------------|------------|
|    Name     |   Formula  |    Result  |
|-------------|------------|------------|
| Commutative |    A ^ B   |    B ^ A   |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1)    |    A ^ 0   |     A      |
|-------------|------------|------------|
| None (2)    |    A ^ A   |     0      |
|-------------|------------|------------|
| None (3)    | (A ^ B) ^ A|     B      |
|-------------|------------|------------|

Nun lassen wir dies beiseite und sehen, was jeder Knoten speichert.

Der erste Knoten oder der Kopf speichert 0 ^ addr (next) da es keinen vorherigen Knoten oder keine Adresse gibt. Es sieht so aus .

Dann speichert der zweite Knoten addr (prev) ^ addr (next) . Es sieht so aus .

Das Ende der Liste, hat keine nächsten Knoten, so speichert er addr (prev) ^ 0 . Es sieht so aus .

Vom Kopf zum nächsten Knoten wechseln

Nehmen wir an, Sie befinden sich jetzt am ersten Knoten oder am Knoten A. Nun möchten Sie sich am Knoten B bewegen. Dies ist die Formel dafür:

Address of Next Node = Address of Previous Node ^ pointer in the current Node

Das wäre also:

addr (next) = addr (prev) ^ (0 ^ addr (next))

Da dies der Kopf ist, wäre die vorherige Adresse einfach 0, also:

addr (next) = 0 ^ (0 ^ addr (next))

Wir können die Klammern entfernen:

addr (next) = 0 ^ 0 addr (next)

Mit der none (2) -Eigenschaft können wir sagen, dass 0 ^ 0 immer 0 ist:

addr (next) = 0 ^ addr (next)

Mit der none (1) -Eigenschaft können wir sie wie folgt vereinfachen:

addr (next) = addr (next)

Sie haben die Adresse des nächsten Knotens!

Wechsel von einem Knoten zum nächsten Knoten

Nehmen wir an, wir befinden uns in einem mittleren Knoten, der einen vorherigen und einen nächsten Knoten hat.

Wenden wir die Formel an:

Address of Next Node = Address of Previous Node ^ pointer in the current Node

Ersetzen Sie nun die Werte:

addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))

Klammern entfernen:

addr (next) = addr (prev) ^ addr (prev) ^ addr (next)

Mit der Eigenschaft none (2) können wir Folgendes vereinfachen:

addr (next) = 0 ^ addr (next)

Mit der Eigenschaft none (1) können wir Folgendes vereinfachen:

addr (next) = addr (next)

Und du verstehst es!

Wechsel von einem Knoten zu dem Knoten, in dem Sie sich zuvor befanden

Wenn Sie den Titel nicht verstehen, bedeutet dies im Wesentlichen, dass Sie, wenn Sie sich an Knoten X befanden und jetzt zu Knoten Y verschoben wurden, zu dem zuvor besuchten Knoten oder grundsätzlich zu Knoten X zurückkehren möchten.

Dies ist keine umständliche Aufgabe. Denken Sie daran, dass ich oben erwähnt hatte, dass Sie Ihre Adresse in einer temporären Variablen speichern. Die Adresse des Knotens, den Sie besuchen möchten, liegt also in einer Variablen:

addr (prev) = temp_addr

Wechsel von einem Knoten zum vorherigen Knoten

Dies ist nicht dasselbe wie oben erwähnt. Ich meine damit, Sie waren am Knoten Z, jetzt sind Sie am Knoten Y und möchten zum Knoten X gehen.

Dies ist fast so, als würde man von einem Knoten zum nächsten wechseln. Nur das ist es umgekehrt. Wenn Sie ein Programm schreiben, werden Sie dieselben Schritte ausführen, die ich beim Verschieben von einem Knoten zum nächsten Knoten erwähnt habe, nur dass Sie das frühere Element in der Liste finden, als das nächste Element.

Beispielcode in C

/* C/C++ Implementation of Memory efficient Doubly Linked List */
#include <stdio.h>
#include <stdlib.h>
 
// Node structure of a memory efficient doubly linked list
struct node
{
    int data;
    struct node* npx;  /* XOR of next and previous node */
};
 
/* returns XORed value of the node addresses */
struct node* XOR (struct node *a, struct node *b)
{
    return (struct node*) ((unsigned int) (a) ^ (unsigned int) (b));
}
 
/* Insert a node at the begining of the XORed linked list and makes the
   newly inserted node as head */
void insert(struct node **head_ref, int data)
{
    // Allocate memory for new node
    struct node *new_node  = (struct node *) malloc (sizeof (struct node) );
    new_node->data = data;
 
    /* Since new node is being inserted at the begining, npx of new node
       will always be XOR of current head and NULL */
    new_node->npx = XOR(*head_ref, NULL);
 
    /* If linked list is not empty, then npx of current head node will be XOR 
       of new node and node next to current head */
    if (*head_ref != NULL)
    {
        // *(head_ref)->npx is XOR of NULL and next. So if we do XOR of 
        // it with NULL, we get next
        struct node* next = XOR((*head_ref)->npx,  NULL);
        (*head_ref)->npx = XOR(new_node, next);
    }
 
    // Change head
    *head_ref = new_node;
}
 
// prints contents of doubly linked list in forward direction
void printList (struct node *head)
{
    struct node *curr = head;
    struct node *prev = NULL;
    struct node *next;
 
    printf ("Following are the nodes of Linked List: \n");
 
    while (curr != NULL)
    {
        // print current node
        printf ("%d ", curr->data);
 
        // get address of next node: curr->npx is next^prev, so curr->npx^prev
        // will be next^prev^prev which is next
        next = XOR (prev, curr->npx);
 
        // update prev and curr for next iteration
        prev = curr;
        curr = next;
    }
}
 
// Driver program to test above functions
int main ()
{
    /* Create following Doubly Linked List
       head-->40<-->30<-->20<-->10   */
    struct node *head = NULL;
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    insert(&head, 40);
 
    // print the created list
    printList (head);
 
    return (0);
}

Der obige Code führt zwei grundlegende Funktionen aus: Einfügen und transversal.

insert : Dies erfolgt durch die Funktion insert . Dadurch wird am Anfang ein neuer Knoten eingefügt. Wenn diese Funktion aufgerufen wird, wird der neue Knoten als Kopf und der vorherige Kopf als zweiter Knoten festgelegt.
Traversal: Dies wird von der Funktion printList . Es durchläuft einfach jeden Knoten und gibt den Wert aus.

Beachten Sie, dass XOR von Zeigern nicht durch den C / C ++ - Standard definiert ist. Daher funktioniert die obige Implementierung möglicherweise nicht auf allen Plattformen.

Verweise

Beachten Sie, dass ich eine Menge Inhalt aus meiner eigenen Antwort auf main genommen habe.

Liste überspringen

Listen überspringen sind verknüpfte Listen, mit denen Sie zum richtigen Knoten springen können. Dies ist eine Methode, die viel schneller ist als eine normale, einzeln verknüpfte Liste. Es ist im Grunde eine einfach verknüpfte Liste, aber die Zeiger gehen nicht von einem Knoten zum nächsten, sondern überspringen wenige Knoten. Also der Name "Liste überspringen".

Unterscheidet sich dies von einer einfach verknüpften Liste?

Ja das ist es.

Eine einfach verknüpfte Liste ist eine Liste, bei der jeder Knoten auf den nächsten Knoten zeigt. Eine grafische Darstellung einer einfach verknüpften Liste sieht wie folgt aus:

Eine Übersprungsliste ist eine Liste, bei der jeder Knoten auf einen Knoten zeigt, der möglicherweise danach liegt oder nicht. Eine grafische Darstellung einer Übersprungsliste ist:

Wie funktioniert es?

Die Übersprungsliste ist einfach. Angenommen, wir möchten auf Knoten 3 im obigen Bild zugreifen. Wir können den Weg vom Kopf zum vierten Knoten nicht gehen, da dies nach dem dritten Knoten ist. Wir gehen also vom Kopf zum zweiten und dann zum dritten Knoten.

Eine grafische Darstellung sieht wie folgt aus:

Verweise

http://igoro.com/archive/skip-lists-are-fascinating/

Doppelt verknüpfte Liste

Doppelte verknüpfte Listen sind eine Art verknüpfter Liste . Die Knoten einer doppelt verknüpften Liste haben zwei "Zeiger" auf die anderen Knoten "Nächste" und "Vorherige". Sie wird als doppelt verknüpfte Liste bezeichnet, da jeder Knoten nur zwei "Zeiger" auf andere Knoten hat. Eine doppelt verknüpfte Liste kann einen Kopf- und / oder Endzeiger haben.

         ┌─────────┬─────────┬─────────┐   ┌─────────┬─────────┬─────────┐         
 null ◀──┤previous │  data   │  next   │◀──┤previous │  data   │  next   │         
         │"pointer"│         │"pointer"│──▶│"pointer"│         │"pointer"│──▶ null 
         └─────────┴─────────┴─────────┘   └─────────┴─────────┴─────────┘         
                          ▲                     △                   △              
                     HEAD │                     │     DOUBLE        │              
                                                └──── REFERENCE ────┘

Doppelt verknüpfte Listen sind weniger platzsparend als einfach verknüpfte Listen. Für einige Vorgänge bieten sie jedoch erhebliche Verbesserungen der Zeiteffizienz. Ein einfaches Beispiel ist die get Funktion, die für eine doppelt verknüpfte Liste mit Head- und Tail-Referenz je nach Index des abzurufenden Elements mit head oder tail beginnt. Um eine n Element-Liste zu erhalten, die das n/2 + i indexierte Element abruft, muss eine einfach verknüpfte Liste mit Head- / Tail-Referenzen n/2 + i Knoten durchlaufen, da sie nicht vom Tail "zurückgehen" kann. Eine doppelt verknüpfte Liste mit Head- / Tail-Referenzen muss nur n/2 - i Knoten durchlaufen, da sie vom Tail "zurückgehen" kann und die Liste in umgekehrter Reihenfolge durchlaufen wird.

Beispielcode in C

Ein einfaches SinglyLinkedList-Beispiel in Java

Eine grundlegende Implementierung für eine einfach verknüpfte Liste in Java, die ganzzahlige Werte am Ende der Liste hinzufügen, den ersten Wert aus der Liste entfernen, ein Array von Werten zu einem bestimmten Zeitpunkt zurückgeben und feststellen kann, ob ein bestimmter Wert vorhanden ist In der Liste.

Node.java

package com.example.so.ds;


/**
 * <p> Basic node implementation </p>
 * @since 20161008
 * @author Ravindra HV
 * @version 0.1
 */
public class Node {
    
    private Node next;
    private int value;
    
    public Node(int value) {
        this.value=value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public int getValue() {
        return value;
    }
    
    
}

SinglyLinkedList.java

package com.example.so.ds;


/**
 * <p> Basic single-linked-list implementation </p>
 * @since 20161008
 * @author Ravindra HV
 * @version 0.2
 */
public class SinglyLinkedList {
    
    private Node head;
    private volatile int size;
    
    public int getSize() {
        return size;
    }
    
    public synchronized void append(int value) {
        
        Node entry = new Node(value);
        if(head == null) {
            head=entry;
        }
        else {
            Node temp=head;
            while( temp.getNext() != null) {
                temp=temp.getNext();
            }
            temp.setNext(entry);
        }
        
        size++;
    }
    
    
    public synchronized boolean removeFirst(int value) {
        boolean result = false;
        
        if( head == null ) { // or size is zero..
            // no action
        }
        else if( head.getValue() == value ) {
            head = head.getNext();
            result = true;
        }
        else {

            Node previous = head;
            Node temp = head.getNext();
            while( (temp != null) && (temp.getValue() != value) ) {
                previous = temp;
                temp = temp.getNext();
            }
            
            if((temp != null) && (temp.getValue() == value)) { // if temp is null then not found..
                previous.setNext( temp.getNext() );
                result = true;
            }

        }
        
        if(result) {
            size--;
        }
        
        return result;
        
    }
    
    public synchronized int[] snapshot() {
        Node temp=head;
        int[] result = new int[size];
        for(int i=0;i<size;i++) {
            result[i]=temp.getValue();
            temp = temp.getNext();
        }
        return result;
    }
    
    public synchronized boolean contains(int value) {
        boolean result = false;
        Node temp = head;
        
        while(temp!=null) {
            if(temp.getValue() == value) {
                result=true;
                break;
            }
            temp=temp.getNext();
        }
        return result;
    }
    
}

TestSinglyLinkedList.java

package com.example.so.ds;

import java.util.Arrays;
import java.util.Random;


/**
 * 
 * <p> Test-case for single-linked list</p>
 * @since 20161008
 * @author Ravindra HV
 * @version 0.2
 *
 */
public class TestSinglyLinkedList {

    /**
     * @param args
     */
    public static void main(String[] args) {
        
        SinglyLinkedList singleLinkedList = new SinglyLinkedList();
        
        int loop = 11;
        Random random = new Random();
        
        for(int i=0;i<loop;i++) {
            
            int value = random.nextInt(loop);
            singleLinkedList.append(value);

            System.out.println();
            System.out.println("Append :"+value);
            System.out.println(Arrays.toString(singleLinkedList.snapshot()));
            System.out.println(singleLinkedList.getSize());
            System.out.println();
        }
        
        for(int i=0;i<loop;i++) {
            int value = random.nextInt(loop);
            boolean contains = singleLinkedList.contains(value);
            singleLinkedList.removeFirst(value);
            
            System.out.println();
            System.out.println("Contains :"+contains);
            System.out.println("RemoveFirst :"+value);
            System.out.println(Arrays.toString(singleLinkedList.snapshot()));
            System.out.println(singleLinkedList.getSize());
            System.out.println();
        }
        

    }

}

Modified text is an extract of the original Stack Overflow Documentation

Lizenziert unter CC BY-SA 3.0

Nicht angeschlossen an Stack Overflow

data-structures
Verknüpfte Liste

Suche…

Einführung in verknüpfte Listen

Einfach verknüpfte Liste

XOR-verknüpfte Liste

Warum wird dies als speichereffiziente verknüpfte Liste bezeichnet?

Unterscheidet sich dies von einer doppelt verknüpften Liste?

Wie funktioniert es?

Beispielcode in C

Verweise

Liste überspringen

Unterscheidet sich dies von einer einfach verknüpften Liste?

Wie funktioniert es?

Verweise

Doppelt verknüpfte Liste

Ein einfaches SinglyLinkedList-Beispiel in Java