双链表—Java迭代器和泛型的拓展
双链表作为基础的数据结构和单链表的唯一区别就是有前驱和后继两个指针，使用JavaAPI定义好的Iterator接口可以简易实现迭代器功能，泛型是java语言一个特殊的地方，可以理解指代类型的形参，代指任意类型，具体使用方法可以参考如下java代码
import java.util.Iterator;
/**
* 定义列表的接口,所有列表该实现的约定
* 增删改查
* @author Administrator
*
*/
public interface MyList<T> extends Iterator<T>{//<T> 代指任意类型，即泛型的使用
/**
* 增加一个元素
* @param element
*/
void add(T element);
/**
* 根据值，删除一个元素
* @param element
*/
void delete(T element);
/**
* 根据下标删除一个元素
* @param index
*/
void delete(int index);
/**
* 根据下标更新一个元素
* @param index
* @param element
*/
void update(int index, T element);
/**
* 判断线性表中是否包含该元素
* 返回布尔型
* @param element
* @return
*/
boolean contains(T element);
/**
* 返回线性表中与该元素相等的值的下标
* 如果没有返回-1
* @param element
* @return
*/
int index(T element);
}
public class _03DoubleLinkedList<T> implements MyList<T>{
ListNode head = new ListNode(null);
/**
* 头结点_亚元
*/
ListNode tail = new ListNode(null);
/**
* 尾节点_亚元
*/
int size;
/**
* 节点数目
*/
public _03DoubleLinkedList() {
head.next = tail;
tail.pre = head;
}
@Override
public void add(T element) {
//尾部插入新节点的正确姿势四部
ListNode newNode = new ListNode(element);
tail.pre.next = newNode;//断开由前一个节点指向尾部的指针,指向新插入的节点
newNode.next = tail;//连接新节点指向尾节点
newNode.pre = tail.pre;//尾节点原来的前驱为新节点的前驱
tail.pre = newNode;//更新尾节点的前驱为新插入的节点
size++;
}
@Override
public void delete(T element) {
ListNode p = head.next;
while(p != tail) {
if(p.data.equals(element)) {
p.pre.next = p.next;//当前要删除节点的前一个节点的后继指向该节点的下一个节点
p.next.pre = p.pre;//当前节点的前驱指向当前要删除节点的后一个节点的前驱
size--;
break;
}
p = p.next;
}
}
@Override
public void delete(int index) {
if(index < 0 ||index >= size)
return;
int i = 0;
ListNode p = head.next;
while(p != tail) {
if(i == index) {
p.pre.next = p.next;
p.next.pre = p.pre;
size--;
break;
}
p = p.next;
i++;
}
}
@Override
public void update(int index, T element) {
if(index < 0||index >= size)
return;
int i = 0;
ListNode p = head.next;
while(p != tail) {
if(i == index) {
p.data = element;
break;
}
p = p.next;
}
}
@Override
public boolean contains(T element) {
ListNode p = head.next;
while(p != tail) {
if(p.data.equals(element))
return true;
p = p.next;
}
return false;
}
@Override
public int index(T element) {
int i = 0;
ListNode p = head.next;
while(p != tail) {
if(p.data.equals(element))
return i;
p = p.next;
i++;
}
return -1;
}
@Override
public String toString() {//头指针和尾指针都为亚元不需要输出
StringBuilder sb = new StringBuilder("[");
ListNode p = head.next;
while(p != tail) {
if(p.next != tail) {
sb.append(p.data + " , ");
}else
sb.append(p.data + "]");
p = p.next;
}
return sb.toString();
}
private ListNode now = head;
@Override
public boolean hasNext() {//判断是否还有下一个值
return now.next != tail;
}
@SuppressWarnings("unchecked")
@Override
public T next() {//每次取下一个值
ListNode next = now.next;
now = now.next;
return (T) next.data;
}
}
测试代码截图：
