JAvaチェーンテーブル構造(一方向、双方向の削除変更)
チェーンテーブルの紹介
チェーンテーブル(Linked list)は一般的な基礎データ構造であり、線形テーブルであるが、線形の順序でデータを格納するのではなく、各ノードに次のノードに格納するポインタ(Pointer)である.
チェーンテーブルと配列の違い
チェーンテーブルと配列は線形テーブル、配列は順序テーブルとも呼ばれ、主な違いは、順序テーブルはメモリに連続した空間を開いてデータを格納し、チェーンテーブルはポインタで複数の不連続(連続)の空間を接続し、論理的に連続した空間を形成してデータを格納することである.2つにはそれぞれメリットがあり、チェーンテーブルの削除や挿入が容易で、テーブルに沿って並べ替えが容易であるなどです.
たんせんチェーンけい
原文リンク:JAVA一方向チェーンテーブルの操作(ノードの追加、ノードの検索、ノードの削除)
主な実装方法:再帰
にほうこうチェーンテーブル
原文リンク:JAVA双方向チェーンテーブルを実現
主な実装方法:前後ノードの置き換え
出力:
[張曼玉、鐘楚紅、劉嘉玲]
[林青霞、張曼玉、鐘楚紅、劉嘉玲]
[林青霞、張曼玉、鐘楚紅、劉嘉玲、梅艶芳]
[林青霞、張曼玉、鐘楚紅、劉嘉玲、王祖賢、梅艶芳]
[張曼玉、鐘楚紅、劉嘉玲、王祖賢、梅艶芳]
[張曼玉、鐘楚紅、劉嘉玲、王祖賢]
[張曼玉、鐘楚紅、王祖賢]
鐘楚紅
チェーンテーブル(Linked list)は一般的な基礎データ構造であり、線形テーブルであるが、線形の順序でデータを格納するのではなく、各ノードに次のノードに格納するポインタ(Pointer)である.
チェーンテーブルと配列の違い
チェーンテーブルと配列は線形テーブル、配列は順序テーブルとも呼ばれ、主な違いは、順序テーブルはメモリに連続した空間を開いてデータを格納し、チェーンテーブルはポインタで複数の不連続(連続)の空間を接続し、論理的に連続した空間を形成してデータを格納することである.2つにはそれぞれメリットがあり、チェーンテーブルの削除や挿入が容易で、テーブルに沿って並べ替えが容易であるなどです.
たんせんチェーンけい
原文リンク:JAVA一方向チェーンテーブルの操作(ノードの追加、ノードの検索、ノードの削除)
主な実装方法:再帰
class Link { //
class Node { // ，
private String data; //
private Node next; //
public Node(String data) { //
this.data = data;
}
public void add(Node node) { //
if (this.next == null) { // ， next
this.next = node;
} else { // ， next
this.next.add(node);
}
}
public void print() { //
if (this.next != null) {
System.out.print(this.data + "-->");
this.next.print();
} else {
System.out.print(this.data + "
");
}
}
public boolean search(String data) { //
if (this.data.equals(data)) {
return true;
}
if (this.next != null) {
return this.next.search(data);
} else {
return false;
}
}
public void delete(Node previous, String data) { //
if (this.data.equals(data)) {
previous.next = this.next;
} else {
if (this.next != null) {
this.next.delete(this, data);
}
}
}
}
private Node root; //
public void addNode(String data) { //
Node newNode = new Node(data); //
if (this.root == null) { // ，
this.root = newNode;
} else { // ，
this.root.add(newNode);
}
}
public void print() { //
if (root != null) { //
this.root.print();
}
}
public boolean searchNode(String data) { //
return root.search(data); //
}
public void deleteNode(String data) { //
if (root.data.equals(data)) { //
if (root.next != null) {
root = root.next;
} else {
root = null;
}
} else {
root.next.delete(this.root, data);
}
}
}
public class LinkDemo {
public static void main(String[] args) {
Link l = new Link();
l.addNode("A");
l.addNode("B");
l.addNode("C");
l.addNode("D");
System.out.println(" ：");
l.print();
String searchNode = "B";
System.out.println(" :" + searchNode);
String result = l.searchNode(searchNode) ? " !" : " !";
System.out.println(" ：" + result);
System.out.println(" ：" + searchNode);
l.deleteNode(searchNode);
System.out.println(" ：");
l.print();
}
}にほうこうチェーンテーブル
原文リンク:JAVA双方向チェーンテーブルを実現
主な実装方法:前後ノードの置き換え
class DoubleLinkedList {
// Node
private static class Node {
Object value;
Node prev = this;
Node next = this;
Node(Object v) {
value = v;
}
public String toString() {
return value.toString();
}
}
private Node head = new Node(null); //
private int size; //
//
public boolean addFirst(Object o) {
addAfter(new Node(o), head);
return true;
}
public boolean addLast(Object o) {
addBefore(new Node(o), head);
return true;
}
public boolean add(Object o) {
return addLast(o);
}
public boolean add(int index, Object o) {
addBefore(new Node(o), getNode(index));
return true;
}
public boolean remove(int index) {
removeNode(getNode(index));
return true;
}
public boolean removeFirst() {
removeNode(head.next);
return true;
}
public boolean removeLast() {
removeNode(head.prev);
return true;
}
public Object get(int index) {
return getNode(index).value;
}
public int size() {
return size;
}
public String toString() {
StringBuffer s = new StringBuffer("[");
Node node = head;
for (int i = 0; i < size; i++) {
node = node.next;
if (i > 0)
s.append(", ");
s.append(node.value);
}
s.append("]");
return s.toString();
}
//
private Node getNode(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException();
Node node = head.next;
for (int i = 0; i < index; i++)
node = node.next;
return node;
}
private void addBefore(Node newNode, Node node) {
newNode.next = node;
newNode.prev = node.prev;
newNode.next.prev = newNode;
newNode.prev.next = newNode;
size++;
}
private void addAfter(Node newNode, Node node) {
newNode.prev = node;
newNode.next = node.next;
newNode.next.prev = newNode;
newNode.prev.next = newNode;
size++;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
size--;
}
}
// ， size ， ， 。
// ：
public class DLinkDemo {
public static void main(String[] args) {
DoubleLinkedList dll = new DoubleLinkedList();
//
dll.add(" ");
dll.add(" ");
dll.add(" ");
System.out.println(dll);
//
dll.addFirst(" ");
System.out.println(dll);
// ，
dll.addLast(" ");
System.out.println(dll);
//
dll.add(4, " ");
System.out.println(dll);
//
dll.removeFirst();
System.out.println(dll);
//
dll.removeLast();
System.out.println(dll);
//
dll.remove(2);
System.out.println(dll);
//
System.out.println(dll.get(1));
}
}出力:
[張曼玉、鐘楚紅、劉嘉玲]
[林青霞、張曼玉、鐘楚紅、劉嘉玲]
[林青霞、張曼玉、鐘楚紅、劉嘉玲、梅艶芳]
[林青霞、張曼玉、鐘楚紅、劉嘉玲、王祖賢、梅艶芳]
[張曼玉、鐘楚紅、劉嘉玲、王祖賢、梅艶芳]
[張曼玉、鐘楚紅、劉嘉玲、王祖賢]
[張曼玉、鐘楚紅、王祖賢]
鐘楚紅