データ構造のリンクリスト-アニメーション

Linked List Data Structures Animation

リンクリストの紹介

リンクリストは非常に一般的なデータ構造であり、ノードで構成されています。各ノードは、データとポインタ（アドレス参照）を格納します。ポインタはノード間の接続を担当します。

これは線形テーブルであり、シーケンシャルストレージとチェーンストレージの2つのストレージ方法があります。リンクリストはリンクストレージに属し、順序は要素間のポインタによって決定されます。要素は非連続的にメモリに保存され、リンクリストの長さは変更できます。配列は、順次格納される線形テーブルです。要素はメモリに継続的に保存され、配列のサイズは作成時に固定されます。

リンクリストは、スタックとキューのデータ構造を実装するために使用でき（スタックとキューは論理データ構造として理解でき、リンクリストはストレージタイプのデータ構造です）、キャッシュLRUアルゴリズムを実装するために使用でき、Javaクラスライブラリもリンクリストを使用します（例： 、LinkedList、LinkedHashMap）など。リンクリストには多くの形式があり、一般的に使用されるのは一方向リンクリスト、双方向リンクリスト、循環リンクリストです...

単一リンクリスト

単一リンクリスト内のノードは、データ（data）と次のノードを指すアドレス（next）の2つの部分に分割され、テールノード（tail）の次はnullを指します。単一リンクリストは、最初から最後までしかトラバースできません。ノードを検索するときは、ヘッドノード（ヘッド）から始めて見下ろす必要があります。
挿入ノードは最初にトラバースして挿入位置を見つけ、次に現在の挿入ノードの次を次のノードにポイントし、前のノードの次を現在の挿入ノードにポイントします。削除されたノードはまた、削除されるノードを見つけるためにトラバースし、次に、現在削除されているノードの次のノードを、現在削除されているノードの次のノードにポイントします。

ノードの擬似コード：

class Node{ private E item private Node next // If it is a tail node, next points to null Node(E data, Node next) { this.item = data this.next = next } // ... }

一方向循環リスト

循環リンクリストは基本的に非循環リンクリストと同じですが、ヘッドノードとテールノードが相互に接続され、次のノードの次のノードがヘッドノードを指し、閉ループを形成する点が異なります。

ノードの擬似コード：

class Node{ private E item // If it is the last node, point to the reference address of the first node private Node next Node(E data, Node next) { this.item = data this.next = next } // ... }

二重リンクリスト

名前が示すように、一方向のリンクリストと比較して、双方向のリンクリストは、データを最初から最後まで、または端から端までトラバースできます。二重リンクリスト内のノードは、前のノードを指すアドレス（prev）とデータ（data）、および次のノードを指すアドレス（next）の3つの部分に分けられます。テールノードの次のノードはnullを指し、ヘッドノード（head）のprevはnullを指します。
ノードの追加と削除は、単一リンクリストと同じですが、前のアドレスを変更する操作のみが追加されます。

ノードの擬似コード：

class Node{ private E item private Node prev // head node prev points to null private Node next // tail node next points to null Node(Node prev, E data, Node next) { this.item = data this.prev = prev this.next = next } // ... }

二重循環リンクリスト

次のテールノードはヘッドノードを指し、前のヘッドノードはテールノードを指し、ヘッドノードとテールノードは互いに接続されて閉ループを形成します。

ノードの擬似コード：

class Node { private E item // If it is the first node, one of them points to the end node private Node prev // If it is the end node, point to the reference address of the first node, forming a ring private Node next Node(Node prev, E data, Node next) { this.item = data this.prev = prev this.next = next } // ... }

リンクリスト操作

リンクリストを追加、削除、変更、確認します。リンクリスト検索ノードは、最初または最後から検索し（一方向リンクリストは最初からしか開始できません）、ノードを削除または挿入して最初にノードを検索してから、関連ノードのポインタを変更する必要があります。 。

例として、二重にリンクされたリストを取り上げます。

ノードの追加

1. 頭にノードを追加します

偽のコード：

Node head Node tail int size // Add a node to the head void addHead(E e) { Node h = head Node newNode = new Node(null, e, h) // (Node prev, E element, Node next) head = newNode if (h == null) {// empty list tail = newNode } else { h.prev = newNode } size ++ // record length }

1. 最後にノードを追加します

偽のコード：

void addTail(E e) { Node t = tail Node newNode = new Node(t, e, null) tail = newNode if(t == null) { head = newNode } else { t.next = newNode } size++ }

1. 位置ごとにノードを挿入

偽のコード：

void add(int index, E element) { if (index == size) { // Add nodes directly at the end } else { // node to find Node temp = null if (index > 1)) {// Due to the doubly linked list, choose to search from the nearest end to the index Node x = head for (int i = 0 i index i--) { x = x.prev } temp = x } // Insert node Node pred = temp.prev Node newNode = new Node(pred, element, temp) temp.prev = newNode if (pred == null) {// The found node is the Head node head = newNode } else { pred.next = newNode } } size++ }

Delete a node

1. ヘッドノードを削除します

偽のコード：

E removeHead() { Node h = head if (h != null){ E element = h.item Node next = h.next head = next if (next == null) { tail = null } else { next.prev = null } size-- // Reduce the length return element // return deleted element } return null }

1. テールノードを削除します

偽のコード：

E removeTail() { Node t = tail if (t != null) { E element = t.item Node prev = t.prev tail = prev if (prev == null) { head = null } else { prev.next = null } size-- return element } return null }

1. ノードの位置または値で削除

擬似コード-場所による削除：

E remove(int index) { // Find nodes according to index Node temp = null if (index > 1)) { Node x = head for (int i = 0 i index i--) { x = x.prev } temp = x } // delete node E element = temp.item Node next = temp.next Node prev = temp.prev if (prev == null) { head = next } else { prev.next = next temp.prev = null } if (next == null) { tail= prev } else { next.prev = prev temp.next = null } temp.item = null size-- return element }

ノードを見つける

1. 位置または値でノードを検索する

擬似コード-ロケーションインデックスによる検索：

E get(int index) { Node temp = null if (index > 1)) {// start searching from the near end Node x = first for (int i = 0 i index i--) { x = x.prev } temp = x } return temp.item }

単一リンクリストの場合は、先頭から逆方向にしか検索できません。

更新ノード

ノードを更新して最初にノードを見つけてから、ノードデータのポインタを変更します。

詳細については、LinkedListのソースコードを参照してください。

リンクリスト実装スタックとキュー

スタックとキューは、データアクセスの厳密な順序要件を持つ線形データ構造であり、リンクリストと配列を使用して実装できます。以下では、リンクリストを使用してスタックとキューを実装しています。

スタック

スタックは一方の端からのみデータにアクセスできます。 後入れ先出し（LIFO） 原則として。スタックに出入りする一方の端はスタックの最上部と呼ばれ、もう一方の閉じた端はスタックの最下部と呼ばれます。

擬似コード-二重にリンクされたリストに基づいて単純な「スタック」を実装します。

class Stack { // return the value of the top element of the stack public E peek() { Node h = head return (h == null) ? null : h.item } // push into the stack public void push(E e) { addHead (e) // Add a node to the head } // Unstack public E pop() { // Remove the head node and return the value return removeHead() } // ... private static class Node { E item Node next Node prev Node(Node prev, E element, Node next) { this.item = element this.next = next this.prev = prev } } }

キュー

キューは両端からデータにアクセスし、一方の端から入り、もう一方の端から出て、次のようになります。 先入れ先出し（FIFO） 原則として。データへのキューの終わりはキューの末尾と呼ばれ、データの終わりはキューの先頭と呼ばれ、キューへのデータはキューと呼ばれ、出力のキューはキューと呼ばれます。

擬似コード-リンクリストに基づいて「キュー」を実装します。

class Queue { // enqueue public boolean offer(E e) { return addTail(e) } // leave the team public E poll() { return removeHead() } // return the value of the header element public E peek() { Node h = head return (h == null) ? null : h.item } private static class Node { E item Node next Node prev Node(Node prev, E element, Node next) { this.item = element this.next = next this.prev = prev } } }

スピードポインター

高速ポインタと低速ポインタは、リンクリストのいくつかの問題を解決するための一般的な方法です。 2つの高速ポインタと低速ポインタアルゴリズムは、次のような多くの問題を解決するために使用されます。

長さが不明な単一リンクリストの最後から2番目のN値を見つけます

リンクリストの長さは不明であるため、最初にリンクリストをループして長さを取得し、次にリンクリストを再度長さ-（N-1）にループして要素を取得します。ただし、高速ポインタと低速ポインタを使用して固定の位置間隔を維持する場合は、リンクリストを循環して要素を見つけるだけで済みます。

偽のコード：

public E getLastN(int n) { Node h = head if (h == null || n <1) { return null } Node fast = h // fast Node slow = h // slow int count = 1 while ((fast = fast.next) != null) { // The penultimate k-th node is n-1 positions away from the penultimate node, so fast goes n-1 positions first if (count++> n - 1) { slow = slow.next } } // The number of elements in the linked list is less than n if (count

リンクリストの中間ノード値を見つける

高速ポインタを低速ポインタの2倍の速度で移動させると、1回のトラバーサルで中間ノードをすばやく見つけることができます。

偽のコード：

public E getMiddle() { Node h = head if (h == null) { return null } Node fast = h // fast Node slow = h // slow while (fast != null && fast.next != null) { fast = fast.next.next // If the length of the linked list is even, there will be two intermediate nodes, and the first one will be returned if (fast != null) { slow = slow.next } } return slow.item }

ソースコード： https://github.com/newobjectcc/code-example/blob/master/basic/Linked.java

また、リンクリストにリングがあるかどうかなども判断できます。スピードポインターはインタビュー中に尋ねられるかもしれません。興味のある友達は、オンラインでリンクリストアルゴリズムの問​​題を見つけることができます。