雙鏈表?

雙鏈表 Java實現資料結構，教程系列

工具/原料

筆記本 eclipse

方法/步驟

建立節點類Node

public class Node {

public T data;

public Node pre;

public Node next;

public Node(T data) {

this.data = data;

this.pre = null;

this.next = null;

}

}

建立雙鏈表DoubleLinkedList ，帶範型

public class DoubleLinkedList {

private Node head;

private Node tail;

private int size;

public DoubleLinkedList() {

head = null;

tail = null;

}

public void addNode(T data){

if(head == null){

head = new Node (data);

tail = head;

size++;

return;

}

Node node = new Node (data);

tail.next = node;

node.pre = tail;

tail = tail.next;//或者寫成 tail = node;

size++;

}

//正序列印

public void print(){

Node curNode = head;

while(curNode!=null){

System.out.print(curNode.data+" ");

curNode = curNode.next;

}

System.out.println();

}

//倒序列印

public void printRerverse(){

Node curNode = tail;

while(curNode!=null){

System.out.print(curNode.data+" ");

curNode = curNode.pre;

}

System.out.println();

}

/**

* 根據索引刪除一個值

* true or false

*/

public boolean deleteNode(int index){

if(index<0 index>size-1){

throw new RuntimeException("刪除異常");

}

if(index==0){ //刪除頭結點

head = head.next;

head.pre = null;

size--;

return true;

}

int count = 1;

Node curNode = head;

while(count

curNode= curNode.next;

count++;

}

Node deleteNode = curNode.next;

curNode.next = deleteNode.next;

if(null==deleteNode.next){ //表示刪除閃到了尾巴節點；

curNode.next = null;

tail = curNode;

}else{

deleteNode.next.pre = curNode;

}

deleteNode.next = null;

deleteNode.pre = null;

size--;

return true;

}

/**

* 插入一個值

*/

public void insertNode(int index,T data){

if(index<0 index>size-1){

throw new RuntimeException("插入新節點異常");

}

if(index==0){//插入頭結點

Node newNode = new Node (data);

newNode.pre = null;

newNode.next = head;

head.pre = newNode;

head = newNode;

size++;

return;

}

int count = 1;

Node curNode = head;

while(count

curNode = curNode.next;//修改引用指向，指向下個節點：

count++;

}

Node nextNode = curNode.next;

Node newNode = new Node (data);

newNode.next = nextNode;

nextNode.pre = newNode;

curNode.next = newNode;

newNode.pre = curNode;

size++;

}

}

編寫測試用例

public class DoubleLinkedListTest {

@Test

public void testPrint() {

DoubleLinkedList doubleLinkedList = new DoubleLinkedList<>();

doubleLinkedList.addNode("abc");

doubleLinkedList.addNode("zhangkai");

doubleLinkedList.addNode("123");

doubleLinkedList.addNode("xyh");

doubleLinkedList.addNode("56hgt");

doubleLinkedList.print();

doubleLinkedList.printRerverse();

}

@Test

public void testDeleteNode() {

DoubleLinkedList doubleLinkedList = new DoubleLinkedList<>();

doubleLinkedList.addNode("abc");

doubleLinkedList.addNode("zhangkai");

doubleLinkedList.addNode("123");

doubleLinkedList.addNode("xyh");

doubleLinkedList.addNode("56hgt");

doubleLinkedList.print();

doubleLinkedList.printRerverse();

doubleLinkedList.deleteNode(0);

doubleLinkedList.print();

doubleLinkedList.printRerverse();

}

@Test

public void testinsertNode() {

DoubleLinkedList doubleLinkedList = new DoubleLinkedList<>();

doubleLinkedList.addNode("abc");

doubleLinkedList.addNode("zhangkai");

doubleLinkedList.addNode("123");

doubleLinkedList.addNode("xyh");

doubleLinkedList.addNode("56hgt");

doubleLinkedList.print();

doubleLinkedList.printRerverse();

doubleLinkedList.insertNode(5, "hehehehehe");

doubleLinkedList.print();

doubleLinkedList.printRerverse();

}

}