线性表
双向链表
定义
双向链表（双链表），多个结点，每个节点=一个数据域+两个指针域，数据域存数据，指针域分前后，前一个指针域指向前驱结点，后一个指针域指向后继结点。头结点数据域不存储数据，头结点指向前驱结点的指针域的值为null，指向后继结点的指针域指向第一个真正存储数据的结点；尾结点指向后继结点的指针域为null。
图示
代码实现
按照面向对象的思想，设计一个类，描述结点，结点属于链表，所有把结点类作为链表类的内部类来实现
链表类
public class DoublyLinkedList<T> implements Iterable{
//头结点
private Node head;
//尾结点
private Node last;
//链表长度（元素实际个数，头结点不算）
private int N;
//--------------------------------------------------
//结点类
private class Node{
//存储数据
public T item;
//指向上一个结点
public Node pre;
//指向下一个结点
public Node next;
//结点类的构造器
public Node( Node pre,T item, Node next) {
this.pre = pre;
this.item = item;
this.next = next;
}
}
//--------------------------------------------------
//构造器
public DoublyLinkedList(){
//初始化头结点和尾结点
this.head = new Node(null,null,null);
this.last = null;
//初始化元素个数
this.N = 0;
}
//--------------------------------------------------
//清空链表
public void clear(){
this.head.pre = null;
this.head.item = null;
this.head.next = null;
this.last = null;
this.N = 0;
}
//--------------------------------------------------
//返回链表长度
public int length(){
return N;
}
//--------------------------------------------------
//判断链表是否为空
public boolean isEmpty(){
return N == 0;
}
//--------------------------------------------------
//获取第一个元素(不是第一个结点，第一个结点不存数据）
public T getFirst(){
if(isEmpty()){
return null;
}
return head.next.item;
}
//--------------------------------------------------
//获取最后一个元素
public T getLast(){
if(isEmpty()){
return null;
}
return last.item;
}
//--------------------------------------------------
//添加元素
public void add(T t){
if(isEmpty()){
//为空
//创建新结点,指向前驱结点，也就是头结点
Node newNode = new Node(head, t,null);
//让新结点成为尾结点
last = newNode;
//让头结点指向尾结点
head.next = last;
}else{
//链表非空
//创建一个oldLast结点代替last，避免冲突
Node oldLast = last;
//创建新结点，指向了当前尾结点
Node newNode = new Node(oldLast, t, null);
//让当前尾结点指向新结点
last.next = newNode;
//让新结点成为尾结点
last = newNode;
}
N++;
}
//--------------------------------------------------
//向指定位置插入元素
public void insert(int i, T t){
//找到i位置的前一个结点
Node preNode = head;
for(int index = 0; index<i; index++){
preNode = preNode.next;
}
//找到i位置的结点
Node currNode = preNode.next;
//创建新结点
Node newNode = new Node(preNode,t,currNode);
//让原i位置的原前一个结点的指向新结点
preNode.next = newNode;
//让i位置的结点指向新结点
currNode.pre = newNode;
//元素个数加1
N++;
}
//--------------------------------------------------
//获取指定位置处的元素
public T get(int i){
Node n = head.next;
for(int index = 0; index<i; index++){
n = n.next;
}
return n.item;
}
//--------------------------------------------------
//找到元素t在链表中第一次出现的位置
public int indexOf(T t){
Node n = head;
for(int i = 0; n.next != null; i++){
n = n.next;
if(n.item.equals(t)){
return i;
}
}
return -1;
}
//--------------------------------------------------
//删除指定位置处的元素，并返回该元素
public T remove(int i){
//找到i位置的前一个结点
Node pre = head;
for(int index = 0; index<i; index++){
pre = pre.next;
}
//找到i位置的结点
Node currNode = pre.next;
//找到i位置的下一个结点
Node nextNode = currNode.next;
//让i位置的前一个节点指向i位置的下一个结点
pre.next = nextNode;
//让i位置的下一个结点指向i位置的前一个节点
nextNode.pre = pre;
//元素个数减1
N--;
return currNode.item;
}
//--------------------------------------------------
@Override
public Iterator iterator() {
return new DIterator();
}
//--------------------------------------------------
//定义内部类实现iterator接口，重写next和hasNext方法
private class DIterator implements Iterator{
private Node n;
public DIterator(){
this.n = head;
}
@Override
public boolean hasNext() {
return n.next != null;
}
@Override
public Object next() {
n = n.next;
return n.item;
}
}
}
测试类
public class DoublyLinkedListTest {
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
dll.add("姚明");
dll.add("科比");
dll.add("乔丹");
//测试迭代遍历
System.out.println("----------------测试遍历--------------------");
for(Object obj : dll){
System.out.println(obj);
}
System.out.println("----------------测试插入--------------------");
dll.insert(1,"杜兰特");
dll.insert(2,"奥尼尔");
for(Object obj : dll){
System.out.println(obj);
}
System.out.println("---------获取第一个和最后一个结点的值------------");
System.out.println(dll.getFirst());;
System.out.println(dll.getLast());
System.out.println("---------获取指定元素第一次出现的位置-------------");
System.out.println(dll.indexOf("科比"));
System.out.println("--------------测试删除----------------------");
System.out.println(dll.remove(2));
System.out.println("--------------清空链表----------------------");
dll.clear();
for(Object obj : dll){
System.out.println(obj);
}
}
}
结果
----------------测试遍历--------------------
姚明
科比
乔丹
----------------测试插入--------------------
姚明
杜兰特
奥尼尔
科比
乔丹
---------获取第一个和最后一个结点的值------------
姚明
乔丹
---------获取指定元素第一次出现的位置-------------
3
--------------测试删除----------------------
奥尼尔
--------------清空链表----------------------