data-structures
Lista enlazada
Buscar..
Introducción a las listas enlazadas
Una lista enlazada es una colección lineal de elementos de datos, llamados nodos, que están vinculados a otro (s) nodo (s) mediante un "puntero". A continuación se muestra una lista enlazada individualmente con una referencia principal.
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴─────────┘ └─────────┴─────────┘
Hay muchos tipos de listas enlazadas, entre ellos por separado y doblemente listas enlazadas y listas enlazadas circulares.
Ventajas
Las listas enlazadas son una estructura de datos dinámica, que puede aumentar y disminuir, asignando y desasignando memoria mientras el programa se está ejecutando.
Las operaciones de inserción y eliminación de nodos se implementan fácilmente en una lista enlazada.
Las estructuras de datos lineales, como pilas y colas, se implementan fácilmente con una lista vinculada.
Las listas enlazadas pueden reducir el tiempo de acceso y pueden expandirse en tiempo real sin sobrecarga de memoria.
Lista enlazada individualmente
Las listas enlazadas individuales son un tipo de lista enlazada . Los nodos de una lista enlazada individualmente solo tienen un "puntero" a otro nodo, generalmente "siguiente". Se denomina lista enlazada individualmente porque cada nodo solo tiene un "puntero" a otro nodo. Una lista enlazada individualmente puede tener una referencia de cabecera y / o cola. La ventaja de tener una referencia de cola son los getFromBack , addToBack y removeFromBack , que se convierten en O (1).
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴────△────┘ └─────────┴─────────┘
SINGLE │
REFERENCE ────┘
Lista enlazada XOR
Una lista enlazada XOR también se conoce como una lista enlazada eficiente en memoria . Es otra forma de una lista doblemente enlazada. Esto depende en gran medida de la puerta lógica XOR y sus propiedades.
¿Por qué esto se llama la lista enlazada de memoria eficiente?
Esto se denomina así porque utiliza menos memoria que una lista tradicional doble vinculada.
¿Es esto diferente de una lista doblemente vinculada?
Si lo es
Una lista de enlace doble almacena dos punteros, que apuntan al siguiente nodo y al anterior. Básicamente, si desea volver, vaya a la dirección señalada con el puntero back . Si desea avanzar, vaya a la dirección señalada por el next puntero. Es como:
Una lista enlazada eficiente en memoria , o la lista enlazada XOR solo tiene un puntero en lugar de dos. Esto almacena la dirección anterior (addr (anterior)) XOR (^) la siguiente dirección (addr (siguiente)). Cuando desee pasar al siguiente nodo, realice ciertos cálculos y busque la dirección del siguiente nodo. Esto es lo mismo para ir al nodo anterior. Es como:
¿Como funciona?
Para entender cómo funciona la lista enlazada, necesita conocer las propiedades de 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 |
|-------------|------------|------------|
Ahora dejemos esto de lado y veamos qué almacena cada nodo.
El primer nodo, o la cabeza , almacena 0 ^ addr (next) ya que no hay ningún nodo o dirección anterior. Se parece a esto .
Luego, el segundo nodo almacena addr (prev) ^ addr (next) . Se parece a esto .
La cola de la lista, no tiene ningún nodo siguiente, por lo que almacena addr (prev) ^ 0 . Se parece a esto .
Pasando de la cabeza al siguiente nodo
Digamos que ahora estás en el primer nodo, o en el nodo A. Ahora quieres moverte en el nodo B. Esta es la fórmula para hacerlo:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
Así que esto sería:
addr (next) = addr (prev) ^ (0 ^ addr (next))
Como esta es la cabecera, la dirección anterior simplemente sería 0, así que:
addr (next) = 0 ^ (0 ^ addr (next))
Podemos eliminar los paréntesis:
addr (next) = 0 ^ 0 addr (next)
Usando la propiedad none (2) , podemos decir que 0 ^ 0 siempre será 0:
addr (next) = 0 ^ addr (next)
Usando la propiedad none (1) , podemos simplificarla para:
addr (next) = addr (next)
Tienes la dirección del siguiente nodo!
Pasando de un nodo al siguiente nodo
Ahora digamos que estamos en un nodo medio, que tiene un nodo anterior y el siguiente.
Apliquemos la fórmula:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
Ahora sustituye los valores:
addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))
Eliminar paréntesis:
addr (next) = addr (prev) ^ addr (prev) ^ addr (next)
Usando la propiedad none (2) , podemos simplificar:
addr (next) = 0 ^ addr (next)
Usando la propiedad none (1) , podemos simplificar:
addr (next) = addr (next)
Y lo entiendes!
Pasando de un nodo al nodo en el que estaba anteriormente
Si no entiende el título, básicamente significa que si estuvo en el nodo X y ahora se ha movido al nodo Y, desea volver al nodo visitado anteriormente, o básicamente al nodo X.
Esto no es una tarea engorrosa. Recuerde que mencioné anteriormente, que almacena la dirección en la que se encontraba en una variable temporal. Por lo tanto, la dirección del nodo que desea visitar está en una variable:
addr (prev) = temp_addr
Mover de un nodo al nodo anterior
Esto no es lo mismo que se mencionó anteriormente. Quiero decir que estabas en el nodo Z, ahora estás en el nodo Y y quieres ir al nodo X.
Esto es casi lo mismo que pasar de un nodo al siguiente nodo. Solo que esto es viceversa. Cuando escriba un programa, utilizará los mismos pasos que mencioné al pasar de un nodo al siguiente, solo que está encontrando el elemento anterior en la lista que el elemento siguiente.
Código de ejemplo en 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);
}
El código anterior realiza dos funciones básicas: inserción y transversal.
Inserción: Esto se realiza mediante la función
insert. Esto inserta un nuevo nodo al principio. Cuando se llama a esta función, coloca el nuevo nodo como cabecera y el nodo anterior como segundo nodo.Traversal: Esto se realiza mediante la función
printList. Simplemente pasa por cada nodo e imprime el valor.
Tenga en cuenta que XOR de punteros no está definido por el estándar C / C ++. Por lo tanto, la implementación anterior puede no funcionar en todas las plataformas.
Referencias
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/
Tenga en cuenta que he tomado un montón de contenido de mi propia respuesta en main.
Omitir lista
Las listas de omisiones son listas vinculadas que le permiten saltar al nodo correcto. Este es un método que es mucho más rápido que una lista enlazada individualmente normal. Básicamente es una lista enlazada individualmente, pero los punteros no van de un nodo al siguiente, sino que omiten algunos nodos. De ahí el nombre "Skip List".
¿Es esto diferente de una lista enlazada individualmente?
Si lo es
Una lista enlazada individualmente es una lista en la que cada nodo apunta al siguiente nodo. Una representación gráfica de una lista enlazada individualmente es como:
Una lista de omisiones es una lista con cada nodo que apunta a un nodo que puede o no estar detrás de él. Una representación gráfica de una lista de omisión es:
¿Como funciona?
La lista de saltos es simple. Digamos que queremos acceder al nodo 3 en la imagen de arriba. No podemos tomar la ruta de ir de la cabeza al cuarto nodo, ya que está después del tercer nodo. Entonces vamos de la cabeza al segundo nodo, y luego al tercero.
Una representación gráfica es como:
Referencias
Lista doblemente vinculada
Las listas enlazadas doblemente son un tipo de lista enlazada . Los nodos de una lista doblemente enlazada tienen dos "punteros" a otros nodos, "siguiente" y "anterior". Se llama lista enlazada doble porque cada nodo solo tiene dos "punteros" a otros nodos. Una lista doblemente enlazada puede tener un puntero de cabeza y / o cola.
┌─────────┬─────────┬─────────┐ ┌─────────┬─────────┬─────────┐
null ◀──┤previous │ data │ next │◀──┤previous │ data │ next │
│"pointer"│ │"pointer"│──▶│"pointer"│ │"pointer"│──▶ null
└─────────┴─────────┴─────────┘ └─────────┴─────────┴─────────┘
▲ △ △
HEAD │ │ DOUBLE │
└──── REFERENCE ────┘
Las listas con enlaces dobles son menos eficientes en espacio que las listas con enlaces individuales; sin embargo, para algunas operaciones, ofrecen mejoras significativas en la eficiencia de tiempo. Un ejemplo simple es la función get , que para una lista doblemente enlazada con una referencia de cabecera y cola comenzará desde la cabecera o la cola, dependiendo del índice del elemento que se obtenga. Para una lista de elementos n , para obtener el elemento indexado n/2 + i , una lista enlazada individualmente con referencias de cabecera / cola debe atravesar los nodos n/2 + i , porque no puede "retroceder" desde la cola. Una lista doblemente enlazada con referencias cabeza / cola solo tiene que atravesar n/2 - i nodos, ya que puede "retroceder" desde la cola, atravesando la lista en orden inverso.
Un ejemplo básico de SinglyLinkedList en Java
Una implementación básica para la lista enlazada individualmente en java - que puede agregar valores enteros al final de la lista, eliminar el primer valor encontrado del valor, devolver una matriz de valores en un instante dado y determinar si un valor dado está presente en la 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();
}
}
}