data-structures
Lista collegata
Ricerca…
Introduzione alle liste collegate
Un elenco collegato è una raccolta lineare di elementi di dati, denominati nodi, che sono collegati ad altri nodi mediante un "puntatore". Di seguito è riportato un elenco collegato separatamente con un riferimento di riferimento.
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴─────────┘ └─────────┴─────────┘
Ci sono molti tipi di liste collegate, tra cui singolarmente e doppiamente liste collegate e liste collegate circolari.
vantaggi
Gli elenchi collegati sono una struttura dati dinamica, che può crescere e restringersi, allocare e deallocare la memoria mentre il programma è in esecuzione.
Le operazioni di inserimento e cancellazione dei nodi sono facilmente implementabili in un elenco collegato.
Strutture di dati lineari come pile e code sono facilmente implementabili con un elenco collegato.
Gli elenchi collegati possono ridurre il tempo di accesso e possono espandersi in tempo reale senza sovraccarico della memoria.
Elenco collegato singolarmente
Gli elenchi collegati singolarmente sono un tipo di elenco collegato . I nodi di una singola lista collegata hanno solo un "puntatore" su un altro nodo, solitamente "successivo". Si chiama elenco collegato singolarmente poiché ogni nodo ha un solo "puntatore" su un altro nodo. Un elenco collegato singolarmente può avere un riferimento di testa e / o coda. Il vantaggio di avere un riferimento di coda sono i casi getFromBack , addToBack e removeFromBack , che diventano O (1).
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴────△────┘ └─────────┴─────────┘
SINGLE │
REFERENCE ────┘
Elenco collegato XOR
Un elenco collegato a XOR è anche chiamato elenco collegato efficiente in memoria . È un'altra forma di una lista doppiamente collegata. Questo dipende fortemente dalla porta logica XOR e dalle sue proprietà.
Perché questo è chiamato Elenco collegato efficiente in termini di memoria?
Questo è chiamato così perché usa meno memoria di una lista tradizionale doppiamente collegata.
È diverso da una lista doppiamente collegata?
Sì , lo è.
Una Lista Doubly-Linked sta memorizzando due puntatori, che puntano al nodo successivo e precedente. In sostanza, se vuoi tornare indietro, vai all'indirizzo indicato dal puntatore back . Se vuoi andare avanti, vai all'indirizzo indicato dal next puntatore. È come:
Un elenco collegato efficiente in memoria , ovvero l' elenco collegato XOR, ha un solo puntatore invece di due. Questo memorizza l'indirizzo precedente (addr (precedente)) XOR (^) l'indirizzo successivo (addr (successivo)). Quando si desidera passare al nodo successivo, si eseguono determinati calcoli e si trova l'indirizzo del nodo successivo. Questo è lo stesso per andare al nodo precedente. È come:
Come funziona?
Per capire come funziona la lista collegata, è necessario conoscere le proprietà di XOR (^):
|-------------|------------|------------|
| 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 |
|-------------|------------|------------|
Ora lasciamo da parte questo e vediamo cosa memorizza ciascun nodo.
Il primo nodo, o la testa , memorizza 0 ^ addr (next) quanto non vi è alcun nodo o indirizzo precedente. Sembra che questo .
Quindi il secondo nodo memorizza addr (prev) ^ addr (next) . Sembra che questo .
La coda della lista, non ha alcun nodo successivo, quindi memorizza addr (prev) ^ 0 . Sembra che questo .
Passaggio da Capo al nodo successivo
Diciamo che ora ci si trova nel primo nodo o nel nodo A. Ora si desidera spostarsi sul nodo B. Questa è la formula per farlo:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
Quindi questo sarebbe:
addr (next) = addr (prev) ^ (0 ^ addr (next))
Poiché questo è il capo, l'indirizzo precedente sarebbe semplicemente 0, quindi:
addr (next) = 0 ^ (0 ^ addr (next))
Possiamo rimuovere le parentesi:
addr (next) = 0 ^ 0 addr (next)
Usando la proprietà none (2) , possiamo dire che 0 ^ 0 sarà sempre 0:
addr (next) = 0 ^ addr (next)
Usando la proprietà none (1) , possiamo semplificarlo per:
addr (next) = addr (next)
Hai l'indirizzo del prossimo nodo!
Passare da un nodo al nodo successivo
Ora diciamo che siamo in un nodo centrale, che ha un nodo precedente e successivo.
Applichiamo la formula:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
Ora sostituisci i valori:
addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))
Rimuovi parentesi:
addr (next) = addr (prev) ^ addr (prev) ^ addr (next)
Usando la proprietà none (2) , possiamo semplificare:
addr (next) = 0 ^ addr (next)
Usando la proprietà none (1) , possiamo semplificare:
addr (next) = addr (next)
E tu capisci!
Passando da un nodo al nodo in cui ci si trovava prima
Se non stai capendo il titolo, in pratica significa che se fossi al nodo X e ora ti sei spostato sul nodo Y, vorrai tornare al nodo visitato in precedenza, o fondamentalmente al nodo X.
Questo non è un compito ingombrante. Ricorda che ho menzionato sopra, che memorizzi l'indirizzo che eri in una variabile temporanea. Quindi l'indirizzo del nodo che vuoi visitare giace in una variabile:
addr (prev) = temp_addr
Passare da un nodo al nodo precedente
Questo non è lo stesso di cui sopra. Intendo dire che eri al nodo Z, ora sei al nodo Y e vuoi andare al nodo X.
Questo è quasi lo stesso del passaggio da un nodo al nodo successivo. Solo che questo è il contrario. Quando scrivi un programma, utilizzerai gli stessi passaggi che ho menzionato nello spostamento da un nodo a un nodo successivo, solo che stai trovando l'elemento precedente nell'elenco piuttosto che trovare l'elemento successivo.
Codice di esempio 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);
}
Il codice sopra riportato esegue due funzioni di base: inserimento e trasversale.
Inserimento: viene eseguito dalla funzione
insert. Questo inserisce un nuovo nodo all'inizio. Quando viene chiamata questa funzione, inserisce il nuovo nodo come head e il nodo head precedente come secondo nodo.Traversal: viene eseguito dalla funzione
printList. Passa semplicemente attraverso ogni nodo e stampa il valore.
Si noti che XOR dei puntatori non è definito dallo standard C / C ++. Quindi l'implementazione sopra potrebbe non funzionare su tutte le piattaforme.
Riferimenti
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/
Nota che ho preso molti contenuti dalla mia risposta su main.
Salta la lista
Gli elenchi Salta sono elenchi collegati che consentono di saltare al nodo corretto. Questo è un metodo molto più veloce di un normale elenco collegato singolarmente. È fondamentalmente una lista collegata singolarmente ma i puntatori non vanno da un nodo all'altro, ma saltano alcuni nodi. Quindi il nome "Skip List".
È diverso da un elenco collegato singolarmente?
Sì , lo è.
Un elenco collegato singolarmente è un elenco con ciascun nodo che punta al nodo successivo. Una rappresentazione grafica di un elenco collegato singolarmente è simile a:
Una lista di salto è una lista con ogni nodo che punta a un nodo che potrebbe o non potrebbe essere dopo di esso. Una rappresentazione grafica di una lista di salto è:
Come funziona?
L'elenco di salto è semplice. Diciamo che vogliamo accedere al nodo 3 nell'immagine qui sopra. Non possiamo prendere la strada per andare dalla testa al quarto nodo, poiché questo è dopo il terzo nodo. Quindi passiamo dalla testa al secondo nodo e poi al terzo.
Una rappresentazione grafica è come:
Riferimenti
Lista Doubly Linked
Gli elenchi collegati doppi sono un tipo di elenco collegato . I nodi di una lista doppiamente collegata hanno due "puntatori" per gli altri nodi, "successivo" e "precedente". Si chiama un doppio elenco collegato perché ogni nodo ha solo due "puntatori" per gli altri nodi. Una lista doppiamente collegata può avere un puntatore a testa e / o coda.
┌─────────┬─────────┬─────────┐ ┌─────────┬─────────┬─────────┐
null ◀──┤previous │ data │ next │◀──┤previous │ data │ next │
│"pointer"│ │"pointer"│──▶│"pointer"│ │"pointer"│──▶ null
└─────────┴─────────┴─────────┘ └─────────┴─────────┴─────────┘
▲ △ △
HEAD │ │ DOUBLE │
└──── REFERENCE ────┘
Le liste collegate doppi sono meno efficienti in termini di spazio rispetto alle liste collegate singolarmente; tuttavia, per alcune operazioni, offrono miglioramenti significativi in termini di efficienza temporale. Un semplice esempio è la funzione get , che per una lista doppiamente collegata con un riferimento di testa e coda inizierà dalla testa o dalla coda a seconda dell'indice dell'elemento da ottenere. Per un elenco di n elementi, per ottenere l'elemento indicizzato n/2 + i , un elenco collegato singolarmente con riferimenti testa / coda deve attraversare n/2 + i nodi, perché non può "tornare indietro" dalla coda. Una lista doppiamente collegata con riferimenti testa / coda deve solo attraversare n/2 - i nodi, perché può "tornare indietro" dalla coda, attraversando la lista in ordine inverso.
Un esempio base di SinglyLinkedList in Java
Un'implementazione di base per l'elenco single-link in java - che può aggiungere valori interi alla fine dell'elenco, rimuovere il primo valore rilevato dall'elenco, restituire un array di valori in un determinato istante e determinare se un dato valore è presente nella lista.
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();
}
}
}