return true;
}
/** 链表的节点类型 */
class Node {
public T data;
public Node pre;// 便于访问的需要，设置为public
public Node next;
public Node() {
};
public Node(Node pre, T data, Node next) {
this.data = data;
this.pre = pre;
this.next = next;
}
}
}
package com.kiritor.linklist;
/**
* java版双向链表的实现
*
* @author Kiritor
*/
public class DBLinkList
// 指向链表的头结点
private Node head;
// 指向链表的尾结点
private Node tail;
private int size = 0;// 链表的元素个数
public DBLinkList() {
this.head = new Node();
this.tail = null;
}
public DBLinkList(T data) {
this.head = new Node(null, data, null);
this.tail = this.head;
this.size++;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return this.size == 0;
}
// 获得链表的长度
public int getLength() {
return this.size;
}
// 获取指定位置结点，下表从0开始
public Node getNode(int index) {
if (index < 0 || index > this.size - 1)
throw new IndexOutOfBoundsException("访问位置非法越界!");
// 根据index所出的位置决定是从前遍历还是从后遍历
if (index <= this.size / 2) {// 位置在前半部分，则从头开始搜索
Node curent = this.head;
for (int i = 0; i <= this.size / 2 && curent != null; i++, curent = curent.next)
if (i == index)
return curent;
} else {// 位置在后半部分，则从后开始往前搜索
Node curent = this.tail;
for (int i = this.size - 1; i > this.size / 2 && curent != null; i--, curent = curent.pre)
if (i == index)
return curent;
}
return null;
}
// 获取指定位置的结点元素
public T getData(int index) {
return this.getNode(index).data;
}
@Override
public T setData(int index, T element) {
return null;
}
// 在链表的头部插入元素，不指定位置默认在头部插入
@Override
public boolean addData(T element) {
// 前驱引用为null,后继引用为头结点
Node node = new Node(null, element, this.head);
this.head.pre = node;// 改变前驱引用
// 修改链表的头结点
this.head = node;
if (tail == null)
tail = this.head;
this.size++;
// System.out.println(head.data+""+this.size);
return true;
}
// 尾部插入
public boolean addTail(T data) {
if (this.head == null) {
this.head = new Node(null, data, null);
this.tail = this.head;
} else {
Node newnode = new Node(this.tail, data, null);
this.tail.next = newnode;
this.tail = newnode;
}
this.size++;
// System.out.println(tail.data+""+this.size);
return true;
}
//下表从0开始
@Override
public boolean addData(int index, T element) {
if (index < 0 || index > this.size)
throw new IndexOutOfBoundsException("不能在该位置插入元素,索引越界");
if (this.head == null)
this.addTail(element);// 尾部插入
else {
if (index == 0)
this.addData(element);// 头部插入
else {
Node prev = this.getNode(index - 1);// 找到index-1处的节点
Node next = prev.next;
Node newnode = new Node(prev, element, next);// 分配节点
prev.next = newnode;
next.pre = newnode;
this.size++;
}
}
return true;
}
public String toString() {
if (this.isEmpty())