data-structures
Połączona lista
Szukaj…
Wprowadzenie do list połączonych
Połączona lista to liniowy zbiór elementów danych, zwanych węzłami, które są połączone z innymi węzłami za pomocą „wskaźnika”. Poniżej znajduje się pojedynczo połączona lista z głównym odniesieniem.
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴─────────┘ └─────────┴─────────┘
Istnieje wiele rodzajów list połączonych, w tym list pojedynczo i podwójnie połączonych oraz list okólnych.
Zalety
Listy połączone to dynamiczna struktura danych, która może się powiększać i zmniejszać, przydzielając i zwalniając pamięć podczas działania programu.
Operacje wstawiania i usuwania węzłów można łatwo zaimplementować na połączonej liście.
Liniowe struktury danych, takie jak stosy i kolejki, można łatwo zaimplementować za pomocą połączonej listy.
Listy połączone mogą skrócić czas dostępu i mogą się rozwijać w czasie rzeczywistym bez narzutu pamięci.
Pojedynczo połączona lista
Pojedynczo połączone listy są rodzajem połączonych list . Węzły pojedynczo połączonej listy mają tylko jeden „wskaźnik” do innego węzła, zwykle „następny”. Nazywa się to pojedynczo połączoną listą, ponieważ każdy węzeł ma tylko jeden „wskaźnik” do innego węzła. Pojedynczo połączona lista może mieć odniesienie do głowy i / lub ogona. Zaletą posiadania odwołania ogona są przypadki getFromBack , addToBack i removeFromBack , które stają się O (1).
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴────△────┘ └─────────┴─────────┘
SINGLE │
REFERENCE ────┘
Przykładowy kod w Javie, z testami jednostkowymi - pojedynczo połączona lista z odnośnikiem głównym
Lista powiązana XOR
Lista połączona XOR jest również nazywana listą połączoną efektywnie korzystającą z pamięci . Jest to kolejna forma podwójnie połączonej listy. Jest to wysoce zależne od bramki logicznej XOR i jej właściwości.
Dlaczego nazywa się to listą efektywnych pamięci?
Nazywa się to tak, ponieważ zużywa mniej pamięci niż tradycyjnie podwójnie połączona lista.
Czy różni się to od listy podwójnie powiązanych?
Tak jest.
Lista podwójnie połączona przechowuje dwa wskaźniki, które wskazują na następny i poprzedni węzeł. Zasadniczo, jeśli chcesz wrócić, idziesz pod adres wskazany przez back wskaźnik. Jeśli chcesz iść do przodu, przejdź do adresu wskazanego przez next wskaźnik. To jest jak:
Lista połączona efektywnie korzystająca z pamięci , a mianowicie lista połączona XOR ma tylko jeden wskaźnik zamiast dwóch. Przechowuje poprzedni adres (adres (poprzedni)) XOR (^) następny adres (adres (następny)). Kiedy chcesz przejść do następnego węzła, wykonaj pewne obliczenia i znajdź adres następnego węzła. To samo dotyczy przejścia do poprzedniego węzła. To jest jak:
Jak to działa?
Aby zrozumieć, jak działa lista połączona, musisz znać właściwości 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 |
|-------------|------------|------------|
Teraz odłóżmy to na bok i zobaczmy, co przechowuje każdy węzeł.
Pierwszy węzeł lub nagłówek przechowuje 0 ^ addr (next) ponieważ nie ma poprzedniego węzła ani adresu. Wygląda jak ten .
Następnie drugi węzeł przechowuje addr (prev) ^ addr (next) . Wygląda jak ten .
Ogon wykazie nie ma żadnego następnego węzła, więc przechowuje addr (prev) ^ 0 . Wygląda jak ten .
Przejście z Head do następnego węzła
Powiedzmy, że jesteś teraz w pierwszym węźle lub w węźle A. Teraz chcesz przejść do węzła B. Oto wzór na to:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
To byłoby:
addr (next) = addr (prev) ^ (0 ^ addr (next))
Ponieważ to jest głowa, poprzedni adres będzie po prostu 0, więc:
addr (next) = 0 ^ (0 ^ addr (next))
Możemy usunąć nawiasy:
addr (next) = 0 ^ 0 addr (next)
Korzystając z właściwości none (2) , możemy powiedzieć, że 0 ^ 0 zawsze będzie równe 0:
addr (next) = 0 ^ addr (next)
Korzystając z właściwości none (1) , możemy uprościć ją do:
addr (next) = addr (next)
Masz adres następnego węzła!
Przenoszenie z węzła do następnego węzła
Powiedzmy teraz, że jesteśmy w środkowym węźle, który ma poprzedni i następny węzeł.
Zastosujmy formułę:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
Teraz podstaw wartości:
addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))
Usuń nawiasy:
addr (next) = addr (prev) ^ addr (prev) ^ addr (next)
Korzystając z właściwości none (2) , możemy uprościć:
addr (next) = 0 ^ addr (next)
Korzystając z właściwości none (1) , możemy uprościć:
addr (next) = addr (next)
I rozumiesz!
Przeniesienie z węzła do węzła, w którym byłeś wcześniej
Jeśli nie rozumiesz tytułu, oznacza to po prostu, że jeśli byłeś w węźle X, a teraz przeniosłeś się do węzła Y, chcesz wrócić do odwiedzonego wcześniej węzła lub zasadniczo do węzła X.
To nie jest kłopotliwe zadanie. Pamiętaj, że wspomniałem powyżej, że przechowujesz adres, pod którym byłeś, w zmiennej tymczasowej. Adres węzła, który chcesz odwiedzić, leży w zmiennej:
addr (prev) = temp_addr
Przeniesienie z węzła do poprzedniego węzła
To nie to samo, co wspomniano powyżej. Mam na myśli to, że byłeś w węźle Z, teraz jesteś w węźle Y i chcesz przejść do węzła X.
To prawie tak samo, jak przejście z węzła do następnego węzła. Po prostu to jest odwrotnie. Kiedy piszesz program, wykonasz te same kroki, o których wspominałem przy przechodzeniu z jednego węzła do następnego, tylko że odnajdujesz wcześniejszy element na liście niż znalezienie następnego.
Przykładowy kod w 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);
}
Powyższy kod pełni dwie podstawowe funkcje: wstawianie i przekrojowe.
Wstawianie: Jest to wykonywane przez
insertfunkcji. To wstawia nowy węzeł na początku. Wywołanie tej funkcji powoduje umieszczenie nowego węzła jako głównego, a poprzedniego węzła głównego jako drugiego.Przechodzenie: Jest to wykonywane przez funkcję
printList. Po prostu przechodzi przez każdy węzeł i wypisuje wartość.
Zauważ, że XOR wskaźników nie jest zdefiniowany przez standard C / C ++. Dlatego powyższa implementacja może nie działać na wszystkich platformach.
Bibliografia
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/
Zauważ, że wziąłem dużo treści z mojej własnej odpowiedzi na main.
Pomiń listę
Listy pomijania to listy połączone, które umożliwiają przejście do właściwego węzła. Jest to metoda znacznie szybsza niż zwykła pojedynczo połączona lista. Jest to w zasadzie pojedynczo połączona lista, ale wskaźniki nie przechodzą z jednego węzła do następnego, ale pomijają kilka węzłów. Stąd nazwa „Lista pominięć”.
Czy różni się to od pojedynczo połączonej listy?
Tak jest.
Pojedynczo połączona lista to lista, której każdy węzeł wskazuje następny węzeł. Graficzna reprezentacja pojedynczo połączonej listy wygląda następująco:
Lista przeskoków to lista, w której każdy węzeł wskazuje na węzeł, który może po nim być lub nie. Graficzna reprezentacja listy pominięć to:
Jak to działa?
Lista pominięć jest prosta. Powiedzmy, że chcemy uzyskać dostęp do węzła 3 na powyższym obrazku. Nie możemy obrać trasy przejścia od głowy do czwartego węzła, ponieważ jest to po trzecim węźle. Idziemy od głowy do drugiego węzła, a następnie do trzeciego.
Graficzna reprezentacja wygląda następująco:
Bibliografia
Podwójnie połączona lista
Podwójnie połączone listy są rodzajem połączonych list . Podwójnie połączone węzły listy mają dwa „wskaźniki” do innych węzłów, „następny” i „poprzedni”. Nazywa się to podwójnie połączoną listą, ponieważ każdy węzeł ma tylko dwa „wskaźniki” do innych węzłów. Podwójnie połączona lista może mieć wskaźnik głowy i / lub ogona.
┌─────────┬─────────┬─────────┐ ┌─────────┬─────────┬─────────┐
null ◀──┤previous │ data │ next │◀──┤previous │ data │ next │
│"pointer"│ │"pointer"│──▶│"pointer"│ │"pointer"│──▶ null
└─────────┴─────────┴─────────┘ └─────────┴─────────┴─────────┘
▲ △ △
HEAD │ │ DOUBLE │
└──── REFERENCE ────┘
Podwójnie połączone listy są mniej wydajne pod względem miejsca niż pojedynczo połączone listy; jednak w przypadku niektórych operacji oferują znaczną poprawę wydajności czasu. Prostym przykładem jest funkcja get , która w przypadku podwójnie połączonej listy z odniesieniem do głowy i ogona rozpocznie się od głowy lub ogona w zależności od indeksu elementu do pobrania. W przypadku listy n elementowej, aby uzyskać element indeksowany n/2 + i , pojedynczo połączona lista z odniesieniami do głowy / ogona musi przechodzić przez węzły n/2 + i , ponieważ nie może ona „cofnąć się” od ogona. Podwójnie połączona lista z odniesieniami do głowy / ogona musi tylko przechodzić przez węzły n/2 - i , ponieważ może „cofać się” od ogona, przesuwając listę w odwrotnej kolejności.
Podstawowy przykład SinglyLinkedList w Javie
Podstawowa implementacja pojedynczo połączonej listy w Javie - która może dodawać wartości całkowite na końcu listy, usuwać pierwszą napotkaną wartość z listy, zwracać tablicę wartości w danym momencie i ustalać, czy dana wartość jest obecna na liście.
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();
}
}
}