(3)双方向チェーンテーブル(Java)
5544 ワード
双方向チェーンテーブルの各ノードは、prevとnextを参照する2つのノードを保持し、prevが現在のノードの前のノードを指し、nextが現在のノードの次のノードを指すようにします.このときのチェーンテーブルは、各ノードに後方にアクセスしたり、各ノードに順次アクセスしたり、各ノードに前にアクセスしたりすることができます.
操作:
①検索:先頭ノードから検索を開始するか、末尾ノードから検索を開始するかは、検索されたノードがヘッダに近いかtailに近いかによって、index②挿入:1つのノードを挿入するには、両方の方向のノードを同時に変更する必要があります.
③削除:1つのノードを削除しても2方向のノードを同時に修正する必要がある
双方向チェーンテーブルは2つの方向のポインタを維持する必要があるため、プログラムはノードを追加したり、ノードを削除したりするのは通常の単一チェーンテーブルを維持するよりも複雑です.
双方向チェーンテーブルの実装は次のとおりです.
操作:
①検索:先頭ノードから検索を開始するか、末尾ノードから検索を開始するかは、検索されたノードがヘッダに近いかtailに近いかによって、index
③削除:1つのノードを削除しても2方向のノードを同時に修正する必要がある
双方向チェーンテーブルは2つの方向のポインタを維持する必要があるため、プログラムはノードを追加したり、ノードを削除したりするのは通常の単一チェーンテーブルを維持するよりも複雑です.
双方向チェーンテーブルの実装は次のとおりです.
package com.xuan.datastructs;
public class DuLinkList<T> {
// Node,Node
private class Node{
//
private T data;
//
private Node prev;
//
private Node next;
//
public Node() {
}
//
public Node(T data,Node prev,Node next){
this.data=data;
this.prev=prev;
this.next=next;
}
}
//
private Node header;
//
private Node tail;
//
private int size;
//
public DuLinkList() {
// ，header tail null
header=null;
tail=null;
}
// ，
public DuLinkList(T element){
header=new Node(element,null,null);
// ，header、tail
tail=header;
size++;
}
//
public int length(){
return size;
}
// index
public T get(int index){
return getNodeByIndex(index).data;
}
// index
private Node getNodeByIndex(int index) {
if(index<0||index>size-1){
throw new IndexOutOfBoundsException(" ");
}
if(index<=size/2){
// header
Node current=header;
for (int i = 0; i <= size/2&¤t!=null; i++,current=current.next) {
if(i==index){
return current;
}
}
}else{
// tail
Node current=tail;
for (int i = size-1; i >size/2&¤t!=null; i++,current=current.prev) {
if(i==index){
return current;
}
}
}
return null;
}
//
public int locate(T element){
//
Node current=header;
for(int i=0;i<size&¤t!=null;i++,current=current.next){
if(current.data.equals(element)){
return i;
}
}
return -1;
}
//
public void insert(T element,int index){
if(index<0||index>size){
throw new IndexOutOfBoundsException(" ");
}
//
if(header==null){
add(element);
}else{
// index 0 ，
if(index==0){
addAtHeader(element);
}else{
//
Node prev=getNodeByIndex(index-1);
//
Node next=prev.next;
// next next ，prev prev
Node newNode=new Node(element,prev,next);
// prev next
prev.next=newNode;
// prev prev
next.prev=newNode;
size++;
}
}
}
//
public void add(T element){
//
if(header==null){
header=new Node(element,null,null);
// ，header、tail
tail=header;
}else{
// ， pre tail
Node newNode=new Node(element,tail,null);
// next
tail.next=newNode;
//
tail=newNode;
}
size++;
}
//
public void addAtHeader(T element){
// ， next header，
header=new Node(element,null,header);
//
if(tail==null){
tail=header;
}
size++;
}
// ,
public T delete(int index){
if(index<0||index>size-1){
throw new IndexOutOfBoundsException(" ");
}
Node del=null;
// header
if(index==0){
del=header;
header=header.next;
// header prev
header.prev=null;
}else{
//
Node prev=getNodeByIndex(index-1);
//
del=prev.next;
// next
prev.next=del.next;
if(del.next!=null){
del.next.prev=prev;
}
// prev、next null
del.prev=null;
del.next=null;
}
size--;
return del.data;
}
//
public T remove(){
return delete(size-1);
}
//
public boolean empty(){
return size==0;
}
//
public void clear(){
// null
header=null;
tail=null;
size=0;
}
public String toString(){
//
if(empty()){
return "[]";
}else{
StringBuilder sb=new StringBuilder("[");
for(Node current=header;current!=null;current=current.next){
sb.append(current.data.toString()+", ");
}
int len=sb.length();
return sb.delete(len-2, len).append("]").toString();
}
}
public String reverseToString(){
//
if(empty()){
return "[]";
}else{
StringBuilder sb=new StringBuilder("[");
for(Node current=tail;current!=null;current=current.prev){
sb.append(current.data.toString()+", ");
}
int len=sb.length();
return sb.delete(len-2, len).append("]").toString();
}
}
//
public static void main(String[] args) {
DuLinkList<String> list=new DuLinkList<String>();
list.insert("a", 0);
list.add("b");
list.insert("c", 0);
// 1
list.insert("d", 1);
//
System.out.println(list);
// 2
list.delete(2);
System.out.println(list);
System.out.println(list.reverseToString());
// c
System.out.println("c ："+list.locate("c"));
System.out.println(" 1 ："+list.get(1));
list.remove();
System.out.println(" remove ："+list);
list.delete(0);
System.out.println(" delete(0) ："+list);
}
}