data-structures
Länkad lista
Sök…
Introduktion till länkade listor
En länkad lista är en linjär samling av dataelement, kallad noder, som är länkade till andra nod (er) med hjälp av en "pekare". Nedan finns en enskilt länkad lista med en huvudreferens.
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴─────────┘ └─────────┴─────────┘
Det finns många typer av länkade listor, inklusive enskilda och dubbelt länkade listor och cirkulära länkade listor.
fördelar
Länkade listor är en dynamisk datastruktur som kan växa och krympa, allokera och omlokalisera minne medan programmet körs.
Insättnings- och raderingsoperationer för nod implementeras enkelt i en länkad lista.
Linjära datastrukturer som staplar och köer implementeras enkelt med en länkad lista.
Länkade listor kan minska åtkomsttiden och kan expanderas i realtid utan minneskostnader.
Singellänkad lista
Singellänkade listor är en typ av länkad lista . En enda länkade listans noder har bara en "pekare" till en annan nod, vanligtvis "nästa." Det kallas en enskilt länkad lista eftersom varje nod bara har en enda "pekare" till en annan nod. En enskilt länkad lista kan ha en huvud- och / eller svansreferens. Fördelen med att ha en getFromBack är getFromBack , addToBack och removeFromBack fall som blir O (1).
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴────△────┘ └─────────┴─────────┘
SINGLE │
REFERENCE ────┘
Exempel Kod i Java, med enhetstester - enskilt länkad lista med huvudreferens
XOR-länkad lista
En XOR-länkad lista kallas också en minneseffektiv länkad lista . Det är en annan form av en dubbel länkad lista. Detta är mycket beroende av XOR- logiken och dess egenskaper.
Varför kallas detta minneseffektiv länkad lista?
Detta kallas så eftersom det använder mindre minne än en traditionell dubbelkopplad lista.
Är det annorlunda från en dubbel länkad lista?
Ja , det är det.
En dubbelkopplad lista lagrar två pekare som pekar på nästa och föregående nod. I grund och botten, om du vill gå tillbaka, går du till den adress som indikeras av back pekaren. Om du vill gå framåt går du till adressen som pekas av next pekare. Det är som:
En minneseffektiv länkad lista , eller nämligen XOR-länkad lista har bara en pekare istället för två. Detta lagrar den föregående adressen (addr (föregående)) XOR (^) nästa adress (addr (nästa)). När du vill flytta till nästa nod gör du vissa beräkningar och hittar adressen till nästa nod. Detta är samma sak för att gå till föregående nod. Det är som:
Hur fungerar det?
För att förstå hur den länkade listan fungerar måste du känna till 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 |
|-------------|------------|------------|
Låt oss nu lämna detta åt sidan och se vad varje nod lagrar.
Den första noden, eller huvudet , lagrar 0 ^ addr (next) eftersom det inte finns någon tidigare nod eller adress. Det ser ut så här .
Sedan lagrar den andra noden addr (prev) ^ addr (next) . Det ser ut så här .
Listans svans har ingen nästa nod, så den lagrar addr (prev) ^ 0 . Det ser ut så här .
Flytta från huvudet till nästa nod
Låt oss säga att du är nu vid den första noden eller vid nod A. Nu vill du flytta vid nod B. Detta är formeln för att göra det:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
Så detta skulle vara:
addr (next) = addr (prev) ^ (0 ^ addr (next))
Eftersom detta är huvudet, skulle den tidigare adressen helt enkelt vara 0, så:
addr (next) = 0 ^ (0 ^ addr (next))
Vi kan ta bort parenteserna:
addr (next) = 0 ^ 0 addr (next)
Med hjälp av none (2) -egenskapen kan vi säga att 0 ^ 0 alltid kommer att vara 0:
addr (next) = 0 ^ addr (next)
Med egenskapen none (1) kan vi förenkla den till:
addr (next) = addr (next)
Du har adressen till nästa nod!
Flytta från en nod till nästa nod
Låt oss nu säga att vi befinner oss i en mittnod som har en föregående och nästa nod.
Låt oss använda formeln:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
Byt nu ut värdena:
addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))
Ta bort pareteser:
addr (next) = addr (prev) ^ addr (prev) ^ addr (next)
Med egenskapen none (2) kan vi förenkla:
addr (next) = 0 ^ addr (next)
Med egenskapen none (1) kan vi förenkla:
addr (next) = addr (next)
Och du får det!
Flytta från en nod till den nod du befann dig tidigare
Om du inte förstår titeln betyder det i princip att om du befann dig i nod X och nu har flyttat till nod Y, vill du gå tillbaka till den nod som besökts tidigare, eller i princip node X.
Detta är inte en besvärlig uppgift. Kom ihåg att jag nämnde ovan, att du lagrar adressen du var på i en tillfällig variabel. Så adressen till den nod du vill besöka ligger i en variabel:
addr (prev) = temp_addr
Flytta från en nod till föregående nod
Detta är inte samma sak som nämnts ovan. Jag menar att säga att du var vid nod Z, nu är du vid nod Y och vill gå till nod X.
Detta är nästan samma sak som att flytta från en nod till nästa nod. Bara att det här är det tvärtom. När du skriver ett program använder du samma steg som jag nämnde vid flyttningen från en nod till nästa nod, bara för att du hittar det tidigare elementet i listan än att hitta nästa element.
Exempelkod i 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);
}
Ovanstående kod utför två grundläggande funktioner: insättning och tvärgående.
Införande: Detta sker genom funktionen
insert. Detta sätter in en ny nod i början. När den här funktionen anropas sätter den den nya noden som huvud och den föregående huvudnoden som den andra noden.Traversal: Detta utförs av funktionen
printList. Den går helt enkelt genom varje nod och skriver ut värdet.
Observera att XOR för pekare inte definieras av C / C ++ -standarden. Så ovanstående implementering kanske inte fungerar på alla plattformar.
referenser
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/
Observera att jag har tagit mycket innehåll från mitt eget svar i huvudsak.
Hoppa över listan
Hoppa över listor är länkade listor som låter dig hoppa till rätt nod. Detta är en metod som är mycket snabbare än en vanlig singellänkad lista. Det är i princip en enskilt länkad lista men pekarna går inte från en nod till nästa nod, utan hoppar över några noder. Således namnet "Skip List".
Är detta annorlunda från en singellänkad lista?
Ja , det är det.
En singellänkad lista är en lista med varje nod som pekar till nästa nod. En grafisk representation av en enskilt länkad lista är som:
En hopplista är en lista med varje nod som pekar på en nod som kanske eller inte kan vara efter den. En grafisk representation av en hopplista är:
Hur fungerar det?
Hoppa över listan är enkel. Låt oss säga att vi vill komma åt nod 3 i bilden ovan. Vi kan inte ta vägen att gå från huvudet till den fjärde noden, eftersom det är efter den tredje noden. Så vi går från huvudet till den andra noden och sedan till den tredje.
En grafisk representation är som:
referenser
Dubbel länkad lista
Dubbelbundna listor är en typ av länkad lista . En dubbel länkad listans noder har två "pekare" till andra noder, "nästa" och "föregående." Det kallas en dubbellänkad lista eftersom varje nod bara har två "pekare" till andra noder. En dubbel länkad lista kan ha en huvud- och / eller svanspekare.
┌─────────┬─────────┬─────────┐ ┌─────────┬─────────┬─────────┐
null ◀──┤previous │ data │ next │◀──┤previous │ data │ next │
│"pointer"│ │"pointer"│──▶│"pointer"│ │"pointer"│──▶ null
└─────────┴─────────┴─────────┘ └─────────┴─────────┴─────────┘
▲ △ △
HEAD │ │ DOUBLE │
└──── REFERENCE ────┘
Dubbelbundna listor är mindre utrymmeeffektiva än enskilda länkade listor; för vissa operationer erbjuder de dock betydande förbättringar i tidseffektivitet. Ett enkelt exempel är get funktionen, som för en dubbel länkad lista med en huvud- och svansreferens kommer att börja från huvud eller svans beroende på index för elementet som ska fås. För en n elementlista, för att få det n/2 + i indexerade elementet, måste en enskilt länkad lista med huvud / svansreferenser gå igenom n/2 + i noder, eftersom den inte kan "gå tillbaka" från svansen. En dubbel länkad lista med huvud- / svansreferenser måste bara korsa n/2 - i noder, eftersom den kan "gå tillbaka" från svansen och korsa listan i omvänd ordning.
Ett grundläggande SinglyLinkedList-exempel i Java
En grundläggande implementering för enskilt länkad lista i java - som kan lägga till heltalvärden i slutet av listan, ta bort det första värdet som uppstått från listan, returnera en matris med ett visst ögonblick och bestämma om ett givet värde är närvarande i listan.
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();
}
}
}