Javaデータ構造のリンクリスト-両端のリンクリスト

Java Data Structure Linked List Double Ended Linked List

リンクリスト

は一般的な基本データ構造であり、線形テーブルですが、データを線形順序で格納するのではなく、各ノードで次のノードポインタ（ポインタ）に格納します。

リンクリスト構造を使用すると、事前にデータサイズを知る必要がある配列リンクリストの欠点を克服できます。リンクリスト構造は、コンピュータのメモリスペースを最大限に活用して、柔軟なメモリ動的管理を実現できます。ただし、リンクリストは配列をランダムに読み取るという利点を失い、ノードのポインタフィールドが追加されるため、リンクリストには大きなスペースオーバーヘッドがあります。

ダブルエンドリンクリスト：

一方向からのみ移動できます。単一リンクリストと比較すると、テールノードへの参照があります。操作にテールノードを追加すると便利です。単一リンクリストでは、テールノードの追加は毎回ヘッドノードからテールにトラバースする必要があります。テールノードが再度追加されます。

サンプルコード：

/** * Created by Administrator on 2019/4/28. */ public class DoublePointLinkedList { Private int size//number of nodes Private Node head//head node Private Node tail//tail node private class Node { private Object data private Node next public Node(Object data) { this.data = data } } public DoublePointLinkedList() { this.size = 0 this.head = null this.tail = null } / / Add a head node public Node addHead(Object data) { Node node = new Node(data) If (size == 0) {//When the linked list is empty Add node Head node == tail node this.head = node this.tail = node } else { node.next = this.head this.head = node } this.size++ return node } / / Add tail node public Node addTail(Object data) { Node node = new Node(data) this.tail.next = node this.tail = node this.size++ return node } / / Is it empty? public boolean isEmpty() { return this.size == 0 } / / Delete the head node public Node delHead() { Node node = this.head if(node.next == null){ this.tail = node.next } this.head = node.next this.size-- return node } / / Delete the tail node public Node delTail() { Node node = this.head while (null != node){ if(null == node.next){ this.head = null this.tail = null return node } if(null == node.next.next){ Node temp = node.next this.tail = node node.next = null return temp } node = node.next } this.size-- return node } / / Query nodes based on node content public Node findObj(Object data) { Node node = this.head while (null != node) { if (data.equals(node.data)) { return node } } return null } / / Display node information public void display() { Node node = this.head System.out.print('[') while (null != node) { Node temp = node.next if (null != temp) { System.out.print(node.data + '->') } else { System.out.print(node.data) } node = temp } System.out.println(']') } }

テストコード：

public class Main { public static void main(String[] args) { // Main.testSingleLinkedList() Main.testDoublePointLinkedList() } private static void testSingleLinkedList(){ SingleLinkedList linkedList = new SingleLinkedList() linkedList.display()//print linkedList.insert(null, linkedList.createNode('A')) linkedList.insert('A', linkedList.createNode('B')) linkedList.insert('B', linkedList.createNode('C')) linkedList.insert('C', linkedList.createNode('D')) linkedList.insert('D', linkedList.createNode('E')) linkedList.display() linkedList.insert('A', linkedList.createNode('A1')) linkedList.display() linkedList.delNodeByObj('A') linkedList.display() } private static void testDoublePointLinkedList(){ DoublePointLinkedList list = new DoublePointLinkedList() list.display() list.addHead('C') list.addHead('B') list.addHead('A') list.display() list.addTail('D') list.addTail('E') list.addTail('F') list.display() list.delHead() list.display() list.delTail() list.display() } }

試験結果：

[] [A->B->C] [A->B->C->D->E->F] [B->C->D->E->F] [B->C->D->E]