data-structures
Gekoppelde lijst
Zoeken…
Inleiding tot gekoppelde lijsten
Een gekoppelde lijst is een lineaire verzameling gegevenselementen, knooppunten genoemd, die via een "pointer" met andere knooppunten zijn verbonden. Hieronder staat een lijst met afzonderlijke links met een hoofdreferentie.
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴─────────┘ └─────────┴─────────┘
Er zijn vele soorten van gelinkte lijsten, met inbegrip van enkelvoudig en dubbel gelinkte lijsten en circulaire gelinkte lijsten.
voordelen
Gekoppelde lijsten zijn een dynamische gegevensstructuur, die kan groeien en krimpen, waarbij geheugen wordt toegewezen en toegewezen terwijl het programma wordt uitgevoerd.
Bewerkingen voor het invoegen en verwijderen van knooppunten kunnen eenvoudig worden geïmplementeerd in een gekoppelde lijst.
Lineaire gegevensstructuren zoals stapels en wachtrijen kunnen eenvoudig worden geïmplementeerd met een gekoppelde lijst.
Gekoppelde lijsten kunnen de toegangstijd verkorten en kunnen in realtime uitbreiden zonder geheugenoverhead.
Afzonderlijk gekoppelde lijst
Afzonderlijk gekoppelde lijsten zijn een soort gekoppelde lijst . De knooppunten van een afzonderlijk gekoppelde lijst hebben slechts één "aanwijzer" naar een andere, meestal "volgende". Het wordt een afzonderlijk gekoppelde lijst genoemd omdat elk knooppunt slechts één "aanwijzer" naar een ander knooppunt heeft. Een afzonderlijk gekoppelde lijst kan een kop- en / of staartreferentie hebben. Het voordeel van een staartreferentie zijn de gevallen getFromBack , addToBack en removeFromBack , die O (1) worden.
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴────△────┘ └─────────┴─────────┘
SINGLE │
REFERENCE ────┘
Voorbeeldcode in Java, met eenheidstests - enkel gekoppelde lijst met hoofdreferentie
XOR gekoppelde lijst
Een XOR Linked-lijst wordt ook een Memory-Efficiënte Linked-lijst genoemd . Het is een andere vorm van een dubbel gekoppelde lijst. Dit is sterk afhankelijk van de logische XOR- poort en zijn eigenschappen.
Waarom wordt dit de geheugen-efficiënte gekoppelde lijst genoemd?
Dit wordt zo genoemd omdat dit minder geheugen gebruikt dan een traditionele, dubbel gekoppelde lijst.
Is dit anders dan een Doubly Linked List?
Ja dat is zo.
Een Doubly-Linked List slaat twee pointers op, die naar het volgende en het vorige knooppunt wijzen. Kortom, als u terug wilt gaan, gaat u naar het adres dat wordt aangegeven door de back aanwijzer. Als u vooruit wilt gaan, gaat u naar het adres dat wordt aangegeven door de next aanwijzer. Het is als:
Een geheugenefficiënte gekoppelde lijst , oftewel de XOR gekoppelde lijst, heeft slechts één aanwijzer in plaats van twee. Dit slaat het vorige adres op (addr (vorige)) XOR (^) het volgende adres (addr (volgende)). Wanneer u naar het volgende knooppunt wilt gaan, voert u bepaalde berekeningen uit en zoekt u het adres van het volgende knooppunt. Dit is hetzelfde om naar het vorige knooppunt te gaan. Het is als:
Hoe werkt het?
Om te begrijpen hoe de gekoppelde lijst werkt, moet u de eigenschappen van 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 |
|-------------|------------|------------|
Laten we dit nu buiten beschouwing laten en kijken wat elke node opslaat.
Het eerste knooppunt of de kop slaat 0 ^ addr (next) omdat er geen vorig knooppunt of adres is. Het lijkt erop dat deze .
Dan slaat het tweede knooppunt addr (prev) ^ addr (next) . Het lijkt erop dat deze .
De staart van de lijst heeft geen volgend knooppunt, dus slaat het addr (prev) ^ 0 . Het lijkt erop dat deze .
Verplaatsen van hoofd naar het volgende knooppunt
Laten we zeggen dat u zich nu bij het eerste knooppunt of bij knooppunt A bevindt. Nu wilt u naar knooppunt B gaan. Dit is de formule om dit te doen:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
Dus dit zou zijn:
addr (next) = addr (prev) ^ (0 ^ addr (next))
Aangezien dit de kop is, zou het vorige adres eenvoudig 0 zijn, dus:
addr (next) = 0 ^ (0 ^ addr (next))
We kunnen de haakjes verwijderen:
addr (next) = 0 ^ 0 addr (next)
Met de eigenschap none (2) kunnen we zeggen dat 0 ^ 0 altijd 0 is:
addr (next) = 0 ^ addr (next)
Met de eigenschap none (1) kunnen we het vereenvoudigen om:
addr (next) = addr (next)
Je hebt het adres van het volgende knooppunt!
Van een knooppunt naar het volgende knooppunt gaan
Laten we nu zeggen dat we ons in een middelste knoop bevinden, met een vorige en volgende knoop.
Laten we de formule toepassen:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
Vervang nu de waarden:
addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))
Haakjes verwijderen:
addr (next) = addr (prev) ^ addr (prev) ^ addr (next)
Met de eigenschap none (2) kunnen we het volgende vereenvoudigen:
addr (next) = 0 ^ addr (next)
Met de eigenschap none (1) kunnen we het volgende vereenvoudigen:
addr (next) = addr (next)
En je snapt het!
Verplaatsen van een knooppunt naar het knooppunt waar u eerder was
Als u de titel niet begrijpt, betekent dit in feite dat als u zich op knooppunt X bevond en nu naar knooppunt Y bent verhuisd, u terug wilt naar het eerder bezochte knooppunt, of eigenlijk knooppunt X.
Dit is geen omslachtige taak. Onthoud dat ik hierboven had gezegd dat u het adres waar u zich bevond in een tijdelijke variabele opsloeg. Het adres van het knooppunt dat u wilt bezoeken, ligt dus in een variabele:
addr (prev) = temp_addr
Verplaatsen van een knooppunt naar het vorige knooppunt
Dit is niet hetzelfde als hierboven vermeld. Ik bedoel dat te zeggen, je was op knooppunt Z, nu ben je op knooppunt Y en wil je naar knooppunt X.
Dit is bijna hetzelfde als het verplaatsen van een knooppunt naar het volgende knooppunt. Alleen dat dit andersom is. Wanneer u een programma schrijft, gebruikt u dezelfde stappen die ik had genoemd bij het verplaatsen van het ene knooppunt naar het volgende knooppunt, alleen dat u het eerdere element in de lijst vindt dan het volgende element.
Voorbeeldcode 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);
}
De bovenstaande code voert twee basisfuncties uit: invoegen en transversaal.
Invoegen: dit wordt uitgevoerd door de functie
insert. Dit voegt aan het begin een nieuw knooppunt in. Wanneer deze functie wordt aangeroepen, wordt de nieuwe knoop als de kop geplaatst en de vorige kop als de tweede knoop.Traversal: dit wordt uitgevoerd door de functie
printList. Het gaat gewoon door elk knooppunt en drukt de waarde af.
Merk op dat XOR van pointers niet wordt gedefinieerd door de C / C ++ standaard. Dus de bovenstaande implementatie werkt mogelijk niet op alle platforms.
Referenties
https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/
http://www.ritambhara.in/memory-efficient-doubly-linked-list/comment-page-1/
http://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-2/
Merk op dat ik veel inhoud heb overgenomen uit mijn eigen hoofdantwoord .
Lijst overslaan
Skiplijsten zijn gekoppelde lijsten waarmee u naar het juiste knooppunt kunt gaan. Dit is een methode die veel sneller is dan een normale afzonderlijk gekoppelde lijst. Het is in feite een afzonderlijk gekoppelde lijst, maar de verwijzingen gaan niet van de ene naar de volgende knoop, maar slaan enkele knooppunten over. Dus de naam "Lijst overslaan".
Is dit anders dan een enkel gekoppelde lijst?
Ja dat is zo.
Een afzonderlijk gekoppelde lijst is een lijst waarbij elk knooppunt naar het volgende knooppunt verwijst. Een grafische weergave van een enkel gekoppelde lijst is als:
Een skiplijst is een lijst waarbij elk knooppunt naar een knooppunt verwijst dat er al dan niet achter staat. Een grafische weergave van een skiplijst is:
Hoe werkt het?
De Skip-lijst is eenvoudig. Laten we zeggen dat we toegang willen hebben tot knooppunt 3 in de bovenstaande afbeelding. We kunnen niet de route nemen om van het hoofd naar het vierde knooppunt te gaan, want dat is na het derde knooppunt. Dus gaan we van het hoofd naar het tweede knooppunt en dan naar het derde.
Een grafische weergave is als:
Referenties
Dubbel gekoppelde lijst
Dubbel gekoppelde lijsten zijn een soort gekoppelde lijst . De knooppunten van een dubbel gekoppelde lijst hebben twee "verwijzingen" naar andere knooppunten, "volgende" en "vorige". Het wordt een dubbel gekoppelde lijst genoemd omdat elk knooppunt slechts twee "verwijzingen" naar andere knooppunten heeft. Een dubbel gekoppelde lijst kan een kop- en / of staartwijzer hebben.
┌─────────┬─────────┬─────────┐ ┌─────────┬─────────┬─────────┐
null ◀──┤previous │ data │ next │◀──┤previous │ data │ next │
│"pointer"│ │"pointer"│──▶│"pointer"│ │"pointer"│──▶ null
└─────────┴─────────┴─────────┘ └─────────┴─────────┴─────────┘
▲ △ △
HEAD │ │ DOUBLE │
└──── REFERENCE ────┘
Dubbel gekoppelde lijsten zijn minder ruimte-efficiënt dan afzonderlijk gekoppelde lijsten; voor sommige bewerkingen bieden ze echter aanzienlijke verbeteringen in tijdsefficiëntie. Een eenvoudig voorbeeld is de get functie, die voor een dubbel gekoppelde lijst met een kop- en staartreferentie begint met kop of staart, afhankelijk van de index van het element dat moet worden opgehaald. Voor een n -element lijst, om de get n/2 + i geïndexeerd element, een enkelvoudig gelinkte lijst met kop / staart referenties moeten doorkruisen n/2 + i nodes, omdat het niet kan "ga terug" van de staart. Een dubbel gekoppelde lijst met kop / staartreferenties hoeft alleen n/2 - i knooppunten te doorlopen, omdat deze van staart "terug" kan gaan en de lijst in omgekeerde volgorde kan doorlopen.
Een eenvoudig SinglyLinkedList-voorbeeld in Java
Een basisimplementatie voor een enkelvoudig gekoppelde lijst in Java - die gehele getallen aan het einde van de lijst kan toevoegen, de eerste aangetroffen waarde uit de lijst kan verwijderen, een reeks waarden op een bepaald moment kan retourneren en bepalen of een gegeven waarde aanwezig is in de lijst.
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();
}
}
}