1、链表实体
public class Link {
public long dData;
public Link next;
public Link previous;
public Link(long d){
dData = d;
}
public void dispalyLink(){
System.out.print(dData + " ");
}
}2、核心代码
public class DoublyLinkedList {
private Link first;
private Link last;
public DoublyLinkedList(){
first = null;
last = null;
}
public boolean isEmpty(){
return first == null;
}
/**
* 向双向链表头插入新的对象
* @param dd
*/
public void insertFirst(long dd){
Link newLink = new Link(dd);//创建新的对象
if(isEmpty()){//如果为空，则最后一个为新的对象
last = newLink;
}else{
first.previous = newLink;//否则，目前第一个的先前一个为新的对象
}
newLink.next = first;//新对象的下一个对象为当前第一个对象
first = newLink;//当前第一个对象指向新的对象
}
/**
* 向链表后尾插入新的对象
* @param dd
*/
public void insertLast(long dd){
Link newLink = new Link(dd);
if(isEmpty()){//如果第一个为空，则第一个对象为新的对象
first = newLink;
}else{
last.next = newLink;//否则最后一个对象的下一个对象为新对象
newLink.previous = last;//新对象的前一个对象为当前最后一个对象
}
last = newLink;//当前最后一个对象指向新的对象
}
/**
* 删除链表第一个对象
* @return
*/
public Link deleteFirst(){
Link temp = first;
if(first.next == null){//如果第一个对象的下一个对象为空，则表明只有一个对象
last = null;//则最后一个对象也置空
}else{//链表的对象个数大于1
first.next.previous = null;//是第一个对象的下一个对象（也就是第二个对象）的前一个对象置空
}
//经过上述步骤，链表的第一个对象已经置为null，加下来是将第一个对象指向原来列表的第二个对象
first = first.next;//将当前第一对象的指向下一个对象（第二个对象）
return temp;
}
/**
* 删除最后一个对象
* @return
*/
public Link deleteLast(){
Link temp = last;
if(first.next == null){//如果第一个对象的下一个对象为空，则表明只有一个对象
first = null;//将第一个置为null，即清空所有列表
}else{//list.size()>1
last.previous.next = null;//让链表最后一个元素的上一个元素的下一个元素置为null（即将最后一个元素置为null）
}
last = last.previous;//将链表的最后一个元素指向原链表的最后一个元素的上一个元素
return temp;
}
/**
* 向某个指定对象候命插入新的对象
* @param key //指定对象
* @param dd //新对象值
* @return
*/
public boolean insertAfter(long key, long dd){
Link current = first;
/**
* 找到指定值的位置
*/
while(current.dData != key){
current = current.next;//找到指定值的位置，并让其为当前对象
if(current == null){
return false;//没有找到指定的对象，返回插入失败
}
}
/**
* 在当前对象后插入新的对象，并完成链路桥接
*/
Link newLink = new Link(dd);//创建新的对象
/**
* 判断是否为最后一个
*/
if(current == last){
newLink.next = null;
last = newLink;//插入链表尾
}else{
newLink.next = current.next;//新对象的下一个对象为当前对象的下一个对象
current.next.previous = newLink;//当前对象的下一个对象的上一个对象变为新对象
}
newLink.previous = current;//新对象的上一个对象为当前对象
current.next = newLink;//当前对象的下一个对象为新对象
return true;//返回插入成功
}
public Link deleteKey(long key){
Link current = first;
/**
* 遍历寻找指定对象
*/
while(current.dData != key){
current = current.next;
if(current == null){
return null;
}
}
/**
* 判断是否为第一个，并桥接下一个对象
*/
if(current == first){//当前对象为第一个对象
first = current.next ;//将第一个对象的指向到原链表第一个对象的下一个对象
}else{
current.previous.next = current.next;//当前对象的上一个对象的一下个对象桥接到当前对象的下一个对象
}
/**
* 判断是否为最后一个，并桥接上一个对象
*/
if(current == last){
last = current.previous;//最后一个对象指向当前对象的上一个对象
}else{
current.next.previous = current.previous;//当前对象的下一个对象的上一个对象桥接到当前对象的上一个对象
}
return current;
}
/**
* 正向遍历列表
*/
public void dispalyForward(){
System.out.print("List (first-->last):");
Link current = first;
while(current != null){
current.dispalyLink();
current = current.next;
}
System.out.println(" ");
}
/**
* 反向遍历列表
*/
public void displayBackward(){
System.out.print("List (last-->first):");
Link current = last;
while(current != null){
current.dispalyLink();
current = current.previous;
}
System.out.println(" ");
}
}3、测试代码
public class DoublyLinkedApp {
@Test
public void test(){
DoublyLinkedList theList = new DoublyLinkedList();
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11);
theList.insertLast(33);
theList.insertLast(55);
theList.dispalyForward();
theList.displayBackward();
theList.deleteFirst();
theList.deleteLast();
theList.deleteKey(11);
theList.dispalyForward();
theList.insertAfter(22, 77);
theList.insertAfter(33, 88);
theList.dispalyForward();
}
}4、运行结果
List (first-->last):66 44 22 11 33 55
List (last-->first):55 33 11 22 44 66
List (first-->last):44 22 33
List (first-->last):44 22 77 33 88 Reference：
[1] Robert Lalore(著) 计晓云，赵研，曾希，狄小菡(译), Java数据结构和算法（第二版）,中国电力出版社，2004 :165-173