data-structures
リンクされたリスト
サーチ…
リンクリストの紹介
リンクされたリストは、ノードと呼ばれるデータ要素の線形集合であり、「ポインタ」によって他のノードにリンクされる。以下は、頭部参照付きの単一リンクリストです。
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴─────────┘ └─────────┴─────────┘
含むリンクされたリストには多くの種類ありますが、 単独および二重リンクリストや循環リンクリストが。
利点
リンクされたリストは動的データ構造であり、プログラムの実行中に拡大縮小、メモリの割り当てと割り当て解除を行うことができます。
ノードの挿入および削除操作は、リンクされたリストに簡単に実装されます。
スタックやキューなどの線形データ構造は、リンクされたリストで簡単に実装できます。
リンクされたリストはアクセス時間を短縮し、メモリオーバヘッドなしでリアルタイムに拡張することができます。
単独リンクリスト
単独でリンクされたリストはの一種であるリンクリスト 。単一リンクリストのノードには、通常は「次へ」という別のノードへのポインタが1つしかありません。各ノードは別のノードへの単一の「ポインタ」しか持たないので、これは単一リンクリストと呼ばれます。単一リンクされたリストは、頭および/または尾の参照を有することができる。テール参照を有することの利点は、 getFromBack 、 addToBack 、及びremoveFromBack Oとなる場合を、（1）。
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴────△────┘ └─────────┴─────────┘
SINGLE │
REFERENCE ────┘
Javaのサンプルコード（単体テストあり） - ヘッド参照付きの単独リンクリスト
XORリンクリスト
XOR Linkedリストは、 Memory-Efficient Linked Listとも呼ばれます。これは二重リンクリストの別の形式です。これは、 XOR論理ゲートおよびその特性に大きく依存する。
これはなぜメモリ効率的なリンクリストと呼ばれていますか？
これは、従来の二重リンクリストより少ないメモリしか使用しないので、これと呼ばれます。
これは二重リンクリストと異なるのですか？
はい 、そうです。
二重リンクリストは、次のノードと前のノードをポイントする2つのポインタを格納しています。基本的に、戻ってくる場合は、 backポインタが指し示すアドレスに行きます。先に進むには、 nextポインタが指すアドレスに移動します。それは次のようなものです：
Memory-Efficient Linked List 、つまりXOR Linked Listには2つではなく1つのポインタしかありません。これは、前のアドレス（addr（prev）） XOR （^）を次のアドレス（addr（next））に格納します。次のノードに移動する場合は、特定の計算を行い、次のノードのアドレスを探します。前のノードに行く場合も同じです。それは次のようなものです：
どのように機能するのですか？
リンクリストの動作を理解するには、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 |
|-------------|------------|------------|
ここでこれを脇に置いて、各ノードが何を格納しているかを見てみましょう。
最初のノードまたはヘッドは、以前のノードまたはアドレスがないので、 0 ^ addr (next)を格納します。それはこのように見えます。
次に、2番目のノードはaddr (prev) ^ addr (next)格納します。それはこのように見えます。
リストの末尾には次のノードがないので、 addr (prev) ^ 0格納しaddr (prev) ^ 0 。それはこのように見えます。
ヘッドから次のノードへの移動
ここで、最初のノードにいるとします。ノードBに移動します。
Address of Next Node = Address of Previous Node ^ pointer in the current Node
これは次のようになります：
addr (next) = addr (prev) ^ (0 ^ addr (next))
これが先頭であるので、前のアドレスは単に0になるので、
addr (next) = 0 ^ (0 ^ addr (next))
かっこは削除できます：
addr (next) = 0 ^ 0 addr (next)
none (2)プロパティを使うと、 0 ^ 0は常に0 ^ 0と言うことができます：
addr (next) = 0 ^ addr (next)
none (1)プロパティを使用すると、次のように単純化できます。
addr (next) = addr (next)
あなたは次のノードのアドレスを持っています！
ノードから次のノードへの移動
さて、私たちが前ノードと次ノードを持つ中間ノードにいるとしましょう。
数式を適用しましょう：
Address of Next Node = Address of Previous Node ^ pointer in the current Node
今度は値を代入してください：
addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))
括弧を削除する：
addr (next) = addr (prev) ^ addr (prev) ^ addr (next)
none (2)プロパティを使用すると、次のように単純化できます。
addr (next) = 0 ^ addr (next)
none (1)プロパティを使用すると、次のように単純化できます。
addr (next) = addr (next)
そしてそれを手に入れよう！
ノードから以前のノードに移動する
タイトルを理解していない場合は、基本的には、ノードXにいて、今ノードYに移動していれば、先に訪れたノード、または基本的にノードXに戻ることを意味します。
これは面倒な作業ではありません。上記で言及したのは、あなたがいたアドレスを一時変数に格納するということです。したがって、訪問したいノードのアドレスは変数にあります：
addr (prev) = temp_addr
ノードから前のノードへの移動
これは上記と同じではありません。私はあなたがノードZにいたと言っています。今はノードYにいて、ノードXに行きたいと思います。
これは、ノードから次のノードへの移動とほぼ同じです。これは逆です。プログラムを書くときは、あるノードから次のノードへ移動する際に述べたのと同じ手順を使用します。リスト内の最初の要素を見つけることは、次の要素を見つけることと同じです。
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);
}
上記のコードは2つの基本的な機能を実行します：挿入と横断。
挿入：これは、関数
insertによって実行されます。これにより、最初に新しいノードが挿入されます。この関数が呼び出されると、新しいノードが先頭になり、前のノードが2番目のノードになります。トラバーサル：これは
printList関数によって実行されます。単に各ノードを通過し、値を出力します。
ポインタのXORはC / C ++標準では定義されていないことに注意してください。したがって、上記の実装はすべてのプラットフォームで動作するわけではありません。
参考文献
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/
私はメインの自分の答えから多くのコンテンツを取ったことに注意してください。
スキップリスト
スキップリストはリンクされたリストで、正しいノードにスキップできます。これは、通常の単一リンクリストよりも高速です。これは基本的には単独でリンクされたリストですが、ポインタはあるノードから次のノードには移動せず、いくつかのノードをスキップします。したがって、名前は「Skip List」となります。
これは単一リンクリストとは異なりますか？
はい 、そうです。
単一リンクリストは、各ノードが次のノードを指し示すリストである。単一リンクされたリストのグラフィカル表現は次のようになります。
スキップリストは、各ノードがそのノードの後にあるかどうかを示すノードを指すリストです。スキップリストの図式表示は次のとおりです。
どのように機能するのですか？
スキップリストは簡単です。上記の画像でノード3にアクセスしたいとしましょう。 3番目のノードの後ろにあるように、頭から4番目のノードに行くルートを取ることはできません。だから私たちは頭から第2のノードに行き、次に第3のノードに行きます。
グラフ表示は次のようになります。
参考文献
二重リンクリスト
二重連結リストはの一種であるリンクリスト 。二重にリンクされたリストのノードは、他のノードへの2つの「ポインタ」、「次の」および「前の」を有する。各ノードは他のノードへの2つの "ポインタ"しか持たないので、これは二重リンクリストと呼ばれます。二重にリンクされたリストは、頭および/または尾のポインタを有することができる。
┌─────────┬─────────┬─────────┐ ┌─────────┬─────────┬─────────┐
null ◀──┤previous │ data │ next │◀──┤previous │ data │ next │
│"pointer"│ │"pointer"│──▶│"pointer"│ │"pointer"│──▶ null
└─────────┴─────────┴─────────┘ └─────────┴─────────┴─────────┘
▲ △ △
HEAD │ │ DOUBLE │
└──── REFERENCE ────┘
二重リンクリストは、一重リンクリストより空間効率が劣ります。ただし、一部の操作では、時間効率の大幅な向上が可能です。簡単な例はget関数です。ヘッドとテールの参照が二重にリンクされたリストの場合、取得する要素のインデックスに応じてheadまたはtailから開始します。 n要素リストの場合、 n/2 + iインデックス要素を取得するには、ヘッド/テール参照を持つ単一リンクリストがn/2 + iノードを通過する必要があります。 head / tail参照を持つ二重リンクリストは、逆順にリストをたどって末尾から "戻る"ことができるので、 n/2 - iノードをたどるだけでよい。
Javaでの基本的なSinglyLinkedListの例
javaの単一リンクリストの基本的な実装 - リストの最後に整数値を追加し、リストから最初に見つかった値を削除し、指定された瞬間に値の配列を返し、指定された値が存在するかどうかを判定しますリスト内の
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();
}
}
}