public class DuLinkList{ private class Node{ private T data; private Node prev; private Node next; @SuppressWarnings("unused") 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 = null; tail = null; } public DuLinkList(T element){ header = new Node(element, null , null); tail = header; size++; } public int length(){ return size; } public T get(int index){ return getNodeByIndex(index).data; } private Node getNodeByIndex(int index) { if(index < 0 || index > size){ throw new IndexOutOfBoundsException("线性表索引越界"); } if(index <= size/2){ //从header节点开始搜索 Node current = header; for(int i = 0 ; i <= size/2 && current != null ; i++ , current = current.next){ if(i == index){ return current; } } } else { //从tail节点开始搜索 Node current = tail; for(int i = size-1 ; i > size/2 && current != 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 && current != 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 { if(index == 0){ addAtHeader(element); } else { Node prev = getNodeByIndex(index - 1); Node next = prev.next; Node newNode = new Node(element , prev , next); prev.next = newNode; next.prev = newNode; size++; } } } private void addAtHeader(T element) { header = new Node(element , null , header); if(tail == null){ tail = header; } size++; } public void add(T element) { if(header == null){ header = new Node(element , null , null); tail = header; } else { Node newNode = new Node(element , tail , null); tail.next = newNode; tail = newNode; } size++; } public T delete(int index){ if(index < 0 || index > size){ throw new IndexOutOfBoundsException("线性表索引越界"); } Node del = null; if(index == 0){ del = header; header = header.next; header.prev = null; del.next = null; } else { Node prev = getNodeByIndex(index - 1); del = prev.next; prev.next = del.next; if(del.next != null){ del.next.prev = del.prev; del.next = null; } del.prev = null; } size--; return del.data; } public T remove(){ return delete(size - 1); } public boolean empty(){ return size == 0; } public void clear(){ 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 class DuLinkListTest { public static void main(String[] args) { DuLinkList list = new DuLinkList (); list.insert("aaaa", 0); list.add("bbbb"); list.insert("cccc", 0); list.insert("dddd", 1); System.out.println(list); list.delete(2); System.out.println(list); System.out.println(list.reverseToString()); System.out.println("cccc在顺序线性表中的位置：" + list.locate("cccc")); System.out.println("链表中索引1处的元素： " + list.get(1)); list.remove(); System.out.println("调用remove方法后的链表： " + list); list.delete(0); System.out.println("调用delete(0)后的链表： " + list); }} 测试结果：
[cccc, dddd, aaaa, bbbb][cccc, dddd, bbbb][bbbb, dddd, cccc]cccc在顺序线性表中的位置：0链表中索引1处的元素： dddd调用remove方法后的链表： [cccc, dddd]调用delete(0)后的链表： [dddd]