简体中文(ZH-CN) English(EN) 繁体中文(ZH-TW) 日本語(JA) 한국어(KO) Melayu(MS) Français(FR) Deutsch(DE)
ホームページ > Java > ＆＃＆チュートリアル > 本文

片端リンク リストおよび両端リンク リスト データ構造の Java シミュレーションの例

高洛峰
リリース： 2017-01-24 16:05:44
オリジナル
1563 人が閲覧しました

単一リンク リストをシミュレートする

線形テーブル:
線形テーブル (シーケンス テーブルとも呼ばれる) は、最も基本的で、最も単純で、最も一般的に使用されるデータ構造です。
線形テーブル内のデータ要素間の関係は 1 対 1 の関係です。つまり、最初と最後のデータ要素を除いて、他のデータ要素は端から端まで接続されます。
線形テーブルの論理構造はシンプルで、実装と操作が簡単です。
実際のアプリケーションでは、線形テーブルは、スタック、キュー、文字列などの特別な線形テーブルの形式で使用されます。
線形構造の基本的な特性は次のとおりです。
1.セットには「最初の要素」が 1 つだけ存在する必要があります。
2.セットには「最後の要素」が 1 つだけ存在する必要があります。
3.最後の要素を除いて、すべての要素には一意の後継者 (結果) があります。最初の要素を除いて、すべての要素には固有の前駆体 (先行要素) があります。

リンク リスト: リンク リスト

リンク リストは、物理ストレージ ユニット上の非連続かつ非順次のストレージ構造です。データ要素の論理的順序は、リンク リスト内のポインターのリンク順序によって実現されます。
各データ項目は次のとおりです。 「チェーン」「ノード」（リンク）に含まれます。
リンクポイントはクラスのオブジェクトであり、Linkと呼ぶことができます。リンク リストには同様のリンク ポイントが多数あり、各リンクには次のリンク ポイントを参照するフィールド next が含まれています。
リンク リスト オブジェクト自体は、最初に最初のリンク ポイントを指す参照を保存します。 (先頭がない場合は配置できません)
リンクリストは配列のように(添え字を使って)データ項目に直接アクセスすることはできませんが、データ間の関係を利用して配置する、つまり次のリンクポイントにアクセスする必要があります。リンク ポイントによって参照され、必要なデータにアクセスするまで次のチェーンに進みます。これは、参照のポインタを変更するだけなので、チェーンの先頭での挿入と削除の時間計算量は O(1) です。そして、挿入後、指定ノードの検索、削除、指定ノードの指定ノードの削除を行うと、平均してリンクリスト内の半分のノードを検索する必要があり、効率はO(N)となります。
単連結リスト:
線形リストを「ノードのシーケンス」として表すことは、線形連結リスト(単連結リスト)と呼ばれます
これは、データ要素を格納するために任意のアドレスを持つ一連の記憶ユニットを使用する、連鎖アクセスのデータ構造です線形リスト内。 (このストレージユニットのグループは連続的または不連続的です)
リンクポイントの構造:


ノード値を格納するデータフィールドデータ(リンクフィールド)。 next片端リンク リストおよび両端リンク リスト データ構造の Java シミュレーションの例リンク リストは、線形リストの n 個のノードを、各ノードのリンク ドメインを通じて論理的な順序でリンクします。

各ノードに 1 つのリンク ドメインのみを持つリンク リストは、一方向に後続のノードへの参照のみが存在します。 

/** 
 * 单链表:头插法 后进先出 
 * 将链表的左边称为链头，右边称为链尾。 
 * 头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。 
 * 头插法最先得到的是尾结点 
 * @author stone 
 */
public class SingleLinkedList<T> { 
    
  private Link<T> first;    //首结点 
  public SingleLinkedList() { 
      
  } 
    
  public boolean isEmpty() { 
    return first == null; 
  } 
    
  public void insertFirst(T data) {// 插入 到 链头 
    Link<T> newLink = new Link<T>(data); 
    newLink.next = first; //新结点的next指向上一结点 
    first = newLink; 
  } 
    
  public Link<T> deleteFirst() {//删除 链头 
    Link<T> temp = first; 
    first = first.next; //变更首结点，为下一结点 
    return temp; 
  } 
    
  public Link<T> find(T t) { 
    Link<T> find = first; 
    while (find != null) { 
      if (!find.data.equals(t)) { 
        find = find.next; 
      } else { 
        break; 
      } 
    } 
    return find; 
  } 
    
  public Link<T> delete(T t) { 
    if (isEmpty()) { 
      return null; 
    } else { 
      if (first.data.equals(t)) { 
        Link<T> temp = first; 
        first = first.next; //变更首结点，为下一结点 
        return temp; 
      } 
    } 
    Link<T> p = first; 
    Link<T> q = first; 
    while (!p.data.equals(t)) { 
      if (p.next == null) {//表示到链尾还没找到 
        return null; 
      } else { 
        q = p; 
        p = p.next; 
      } 
    } 
      
    q.next = p.next; 
    return p; 
  } 
    
  public void displayList() {//遍历 
    System.out.println("List (first-->last):"); 
    Link<T> current = first; 
    while (current != null) { 
      current.displayLink(); 
      current = current.next; 
    } 
  } 
    
  public void displayListReverse() {//反序遍历 
    Link<T> p = first, q = first.next, t; 
    while (q != null) {//指针反向，遍历的数据顺序向后 
      t = q.next; //no3 
      if (p == first) {// 当为原来的头时，头的.next应该置空 
        p.next = null; 
      } 
      q.next = p;// no3 -> no1 pointer reverse 
      p = q; //start is reverse 
      q = t; //no3 start 
    } 
    //上面循环中的if里，把first.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给first 
    first = p;  
    displayList(); 
  } 
    
  class Link<T> {//链结点 
    T data;   //数据域 
    Link<T> next; //后继指针，结点    链域 
    Link(T data) { 
      this.data = data; 
    } 
    void displayLink() { 
      System.out.println("the data is " + data.toString()); 
    } 
  } 
    
  public static void main(String[] args) { 
    SingleLinkedList<Integer> list = new SingleLinkedList<Integer>(); 
    list.insertFirst(33); 
    list.insertFirst(78); 
    list.insertFirst(24); 
    list.insertFirst(22); 
    list.insertFirst(56); 
    list.displayList(); 
      
    list.deleteFirst(); 
    list.displayList(); 
      
    System.out.println("find:" + list.find(56)); 
    System.out.println("find:" + list.find(33)); 
      
    System.out.println("delete find:" + list.delete(99)); 
    System.out.println("delete find:" + list.delete(24)); 
    list.displayList(); 
    System.out.println("----reverse----"); 
    list.displayListReverse(); 
  } 
}
ログイン後にコピー

Print
List (first-->last):
the data is 56
the data is 22
the data is 24
the data is 78
the data is 33
List (first-->last):
the data is 22
the data is 24
the data is 78
the data is 33
find:null
find:linked_list.SingleLinkedList$Link@4b71bbc9
delete find:null
delete find:linked_list.SingleLinkedList$Link@17dfafd1
List (first-->last):
the data is 22
the data is 78
the data is 33
----reverse----
List (first-->last):
the data is 33
the data is 78
the data is 22
ログイン後にコピー

シングル リンク リスト: 末尾挿入メソッド。 -in-first Out - リンク リストの左端が固定され、リンク リストが右に伸び続ける場合、リンク リストを確立するこの方法は末尾挿入と呼ばれます。

末尾補間メソッドが連結リストを作成するとき、先頭ポインタは固定されるため、末尾ポインタは連結リストの右側に拡張するように設定する必要があります。

末尾補間メソッドは、最初に先頭ノードを取得します。 

public class SingleLinkedList2<T> {
    
  private Link<T> head;   //首结点
  public SingleLinkedList2() {
      
  }
    
  public boolean isEmpty() {
    return head == null;
  }
    
  public void insertLast(T data) {//在链尾 插入
    Link<T> newLink = new Link<T>(data);
    if (head != null) {
      Link<T> nextP = head.next;
      if (nextP == null) {
        head.next = newLink;
      } else {
        Link<T> rear = null;
        while (nextP != null) {
          rear = nextP;
          nextP = nextP.next;
        }
        rear.next = newLink;
      }
    } else {
      head = newLink;
    }
  }
    
  public Link<T> deleteLast() {//删除 链尾
    Link<T> p = head;
    Link<T> q = head;
    while (p.next != null) {// p的下一个结点不为空，q等于当前的p(即q是上一个，p是下一个) 循环结束时，q等于链尾倒数第二个
      q = p;
      p = p.next;
    }
    //delete
    q.next = null;
    return p;
  }
    
  public Link<T> find(T t) {
    Link<T> find = head;
    while (find != null) {
      if (!find.data.equals(t)) {
        find = find.next;
      } else {
        break;
      }
    }
    return find;
  }
    
  public Link<T> delete(T t) {
    if (isEmpty()) {
      return null;
    } else {
      if (head.data.equals(t)) {
        Link<T> temp = head;
        head = head.next; //变更首结点，为下一结点
        return temp;
      }
    }
    Link<T> p = head;
    Link<T> q = head;
    while (!p.data.equals(t)) {
      if (p.next == null) {//表示到链尾还没找到
        return null;
      } else {
        q = p;
        p = p.next;
      }
    }
      
    q.next = p.next;
    return p;
  }
    
  public void displayList() {//遍历
    System.out.println("List (head-->last):");
    Link<T> current = head;
    while (current != null) {
      current.displayLink();
      current = current.next;
    }
  }
    
  public void displayListReverse() {//反序遍历
    Link<T> p = head, q = head.next, t;
    while (q != null) {//指针反向，遍历的数据顺序向后
      t = q.next; //no3
      if (p == head) {// 当为原来的头时，头的.next应该置空
        p.next = null;
      }
      q.next = p;// no3 -> no1 pointer reverse
      p = q; //start is reverse
      q = t; //no3 start
    }
    //上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head
    head = p; 
    displayList();
  }
    
  class Link<T> {//链结点
    T data;   //数据域
    Link<T> next; //后继指针，结点    链域
    Link(T data) {
      this.data = data;
    }
    void displayLink() {
      System.out.println("the data is " + data.toString());
    }
  }
    
  public static void main(String[] args) {
    SingleLinkedList2<Integer> list = new SingleLinkedList2<Integer>();
    list.insertLast(33);
    list.insertLast(78);
    list.insertLast(24);
    list.insertLast(22);
    list.insertLast(56);
    list.displayList();
      
    list.deleteLast();
    list.displayList();
      
    System.out.println("find:" + list.find(56));
    System.out.println("find:" + list.find(33));
      
    System.out.println("delete find:" + list.delete(99));
    System.out.println("delete find:" + list.delete(78));
    list.displayList();
    System.out.println("----reverse----");
    list.displayListReverse();
  }
}
ログイン後にコピー


Print

List (head-->last):
the data is 33
the data is 78
the data is 24
the data is 22
the data is 56
List (head-->last):
the data is 33
the data is 78
the data is 24
the data is 22
find:null
find:linked_list.SingleLinkedList2$Link@4b71bbc9
delete find:null
delete find:linked_list.SingleLinkedList2$Link@17dfafd1
List (head-->last):
the data is 33
the data is 24
the data is 22
----reverse----
List (head-->last):
the data is 22
the data is 24
the data is 33
ログイン後にコピー

両端リンク リストをシミュレートし、リンク リストを使用してスタックとキューを実装します

両端リンク リスト:

両端リンク リストは、以下に非常に似ています。従来のリンク リストでは、新しい属性、つまり最後のリンク ノードの後方を追加するだけです

この方法では、後方の次を変更するだけで済みます。新しいノード。最後のノードを検索するループは必要ありません
したがって、insertFirst、insertLastがあります
チェーンの先頭を削除する場合、チェーンの終端を削除する場合は、参照点を変更するだけで済みます。最後から 2 番目のノードの次のノードを空にします
それを指す参照がないため、操作を読み取るためにループする必要があります 

/**
 * 双端链表
 * @author stone
 */
public class TwoEndpointList<T> {
  private Link<T> head;   //首结点
  private Link<T> rear;   //尾部指针
    
  public TwoEndpointList() {
      
  }
    
  public T peekHead() {
    if (head != null) {
      return head.data;
    }
    return null;
  }
    
  public boolean isEmpty() {
    return head == null;
  }
    
  public void insertFirst(T data) {// 插入 到 链头
    Link<T> newLink = new Link<T>(data);
    newLink.next = head; //新结点的next指向上一结点
    head = newLink;
  }
    
  public void insertLast(T data) {//在链尾 插入
    Link<T> newLink = new Link<T>(data);
    if (head == null) {
      rear = null;
    }
    if (rear != null) {
      rear.next = newLink;
    } else {
      head = newLink;
      head.next = rear;
    }
    rear = newLink; //下次插入时，从rear处插入
      
  }
    
  public T deleteHead() {//删除 链头
    if (isEmpty()) return null;
    Link<T> temp = head;
    head = head.next; //变更首结点，为下一结点
    if (head == null) {
    <span style="white-space:pre">  </span>rear = head;
    }
    return temp.data;
  }
    
  public T find(T t) {
    if (isEmpty()) {
      return null;
    }
    Link<T> find = head;
    while (find != null) {
      if (!find.data.equals(t)) {
        find = find.next;
      } else {
        break;
      }
    }
    if (find == null) {
      return null;
    }
    return find.data;
  }
    
  public T delete(T t) {
    if (isEmpty()) {
      return null;
    } else {
      if (head.data.equals(t)) {
        Link<T> temp = head;
        head = head.next; //变更首结点，为下一结点
        return temp.data;
      }
    }
    Link<T> p = head;
    Link<T> q = head;
    while (!p.data.equals(t)) {
      if (p.next == null) {//表示到链尾还没找到
        return null;
      } else {
        q = p;
        p = p.next;
      }
    }
    q.next = p.next;
    return p.data;
  }
    
  public void displayList() {//遍历
    System.out.println("List (head-->last):");
    Link<T> current = head;
    while (current != null) {
      current.displayLink();
      current = current.next;
    }
  }
    
  public void displayListReverse() {//反序遍历
    if (isEmpty()) {
      return;
    }
    Link<T> p = head, q = head.next, t;
    while (q != null) {//指针反向，遍历的数据顺序向后
      t = q.next; //no3
      if (p == head) {// 当为原来的头时，头的.next应该置空
        p.next = null;
      }
      q.next = p;// no3 -> no1 pointer reverse
      p = q; //start is reverse
      q = t; //no3 start
    }
    //上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head
    head = p; 
    displayList();
  }
    
  class Link<T> {//链结点
    T data;   //数据域
    Link<T> next; //后继指针，结点    链域
    Link(T data) {
      this.data = data;
    }
    void displayLink() {
      System.out.println("the data is " + data.toString());
    }
  }
    
  public static void main(String[] args) {
    TwoEndpointList<Integer> list = new TwoEndpointList<Integer>();
    list.insertLast(1);
    list.insertFirst(2);
    list.insertLast(3);
    list.insertFirst(4);
    list.insertLast(5);
    list.displayList();
      
    list.deleteHead();
    list.displayList();
      
    System.out.println("find:" + list.find(6));
    System.out.println("find:" + list.find(3));
  
    System.out.println("delete find:" + list.delete(6));
    System.out.println("delete find:" + list.delete(5));
    list.displayList();
    System.out.println("----reverse----");
    list.displayListReverse();
  }
}
ログイン後にコピー


Print

List (head-->last):
the data is 4
the data is 2
the data is 1
the data is 3
the data is 5
List (head-->last):
the data is 2
the data is 1
the data is 3
the data is 5
find:null
find:3
delete find:null
delete find:5
List (head-->last):
the data is 2
the data is 1
the data is 3
----reverse----
List (head-->last):
the data is 3
the data is 1
the data is 2
ログイン後にコピー

実装するにはリンク リストを使用しますスタック。これは、前方単一リンク リストを挿入することで実現できます。

このクラスは、ダブルエンド リンク リストを使用して以下を実装します。


Print 

public class LinkStack<T> {
  private TwoEndpointList<T> datas;
    
  public LinkStack() {
    datas = new TwoEndpointList<T>();
  }
    
  // 入栈
  public void push(T data) {
    datas.insertFirst(data);
  }
    
  // 出栈
  public T pop() {
    return datas.deleteHead();
  }
    
  // 查看栈顶
  public T peek() {
    return datas.peekHead();
  }
    
  //栈是否为空
  public boolean isEmpty() {
    return datas.isEmpty();
  }
    
  public static void main(String[] args) {
    LinkStack<Integer> stack = new LinkStack<Integer>();
    for (int i = 0; i < 5; i++) {
      stack.push(i);
    }
    for (int i = 0; i < 5; i++) {
      Integer peek = stack.peek();
      System.out.println("peek:" + peek);
    }
    for (int i = 0; i < 6; i++) {
      Integer pop = stack.pop();
      System.out.println("pop:" + pop);
    }
      
    System.out.println("----");
    for (int i = 5; i > 0; i--) {
      stack.push(i);
    }
    for (int i = 5; i > 0; i--) {
      Integer peek = stack.peek();
      System.out.println("peek:" + peek);
    }
    for (int i = 5; i > 0; i--) {
      Integer pop = stack.pop();
      System.out.println("pop:" + pop);
    }
  }
}
ログイン後にコピー

リンク リストを使用したキューの実装 ダブルエンド リンク リストを使用した実装。リンク リスト: 

peek:4
peek:4
peek:4
peek:4
peek:4
pop:4
pop:3
pop:2
pop:1
pop:0
pop:null
----
peek:1
peek:1
peek:1
peek:1
peek:1
pop:1
pop:2
pop:3
pop:4
pop:5
ログイン後にコピー

Print

public class LinkQueue<T> {
  private TwoEndpointList<T> list;
    
  public LinkQueue() {
    list = new TwoEndpointList<T>();
  }
  //插入队尾
  public void insert(T data) {
    list.insertLast(data);
  }
  //移除队头
  public T remove() {
    return list.deleteHead();
  }
  //查看队头
  public T peek() {
    return list.peekHead();
  }
    
  public boolean isEmpty() {
    return list.isEmpty();
  }
    
  public static void main(String[] args) {
    LinkQueue<Integer> queue = new LinkQueue<Integer>();
    for (int i = 1; i < 5; i++) {
      queue.insert(i);
    }
    for (int i = 1; i < 5; i++) {
      Integer peek = queue.peek();
      System.out.println("peek:" + peek);
    }
    for (int i = 1; i < 5; i++) {
      Integer remove = queue.remove();
      System.out.println("remove:" + remove);
    }
      
    System.out.println("----");
      
    for (int i = 5; i > 0; i--) {
      queue.insert(i);
    }
    for (int i = 5; i > 0; i--) {
      Integer peek = queue.peek();
      System.out.println("peek2:" + peek);
    }
    for (int i = 5; i > 0; i--) {
      Integer remove = queue.remove();
      System.out.println("remove:" + remove);
    }
  }
}
ログイン後にコピー

片リンク リストおよび両端リンク リスト データ構造の Java シミュレーションのその他の例については、PHP 中国語 Web サイトの関連記事に注目してください。

関連ラベル：
Java 链表
ソース：php.cn
前の記事：順序付きリンク リスト データ構造をシミュレートする Java の例 次の記事：Javaは単連結リストと二重連結リストを実装します。
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
最新の問題
特定のクリック イベントをリッスンし、他のクリック イベントを抑制するにはどうすればよいですか? 私の Web アプリケーションには、各行が特定の URL にリンクする HTML テーブルが含まれています: <table><trdata-url="h...
から 2024-04-04 16:55:27
0
1
317
CSS スタイルシートが機能しなくなり、HTML ファイルにリンクしなくなりました。原因は何でしょうか? 多くのフォーラムで答えを探し、約 50 の Google リンクを調べましたが、有効なものが見つかりませんでした。CSS が HTML に表示されません。私のコードは、フレックスボ...
から 2024-04-03 09:49:45
0
1
402
CSS: リスト項目間の間隔を変更する リストの CSS を編集しようとしましたが、行に正しく移動してリスト要素間の高さを調整する方法が見つかりませんでした。ウェブサイトのリンク: https://denkimedia....
から 2024-04-02 15:46:38
0
1
342
要素内で複数の項目を整列する: ステップバイステップのガイド 一つの要素内に異なるアイテムを並べたい！ Elementにフレックスボックスを与えて中の項目を自分で調整してみました！しかし、正しく反応しません！リスト項目は、左のリンクが左側に、...
から 2024-04-01 23:21:40
0
2
366
トースト UI ホームページに似たナビゲーション バーを作成する 私のインスピレーションの源は、次のようなナビゲーション バーを作りたいと思っていました。 Toastui ホームページ 私がやったこと これを実現するために、できる限りコピーしよう...
から 2024-04-01 18:34:38
0
1
240
関連トピック
詳細>
人気のおすすめ
人気のチュートリアル
詳細>
関連するチュートリアル
人気のおすすめ
最新のコース
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート
私たちについて 免責事項 Sitemap
PHP中国語ウェブサイト：福祉オンライン PHP トレーニング，PHP 学習者の迅速な成長を支援します！