package algorithm3;
import java.util.Iterator;
public class TwoWayLinkList implements Iterable{
//定义双向链表的成员变量
private Node head; //记录首结点
private Node last; //记录尾结点
private int N; //记录链表内元素个数
//首先定义一个内部类,结点类
private class Node {
//内部类(Node)的成员变量
private Node pre;
private Node next;
private T item;
//内部类(Node)的构造方法
public Node(T item,Node pre,Node next) {
this.pre = pre;
this.next = next;
this.item = item;
}
}
//构造方法,即初始化双向链表
public TwoWayLinkList() {
this.head = new Node(null,null,null);
this.last = null;
this.N = 0;
}
//双向链表的成员方法
//1.清空链表
public void clear() {
//1.让头结点不往后指,让last结点为空,让元素个数为0
head.next =null;
last = null;
N = 0;
}
//2.获取链表长度
public int length() {
return N;
}
//3.判断链表是否为空
public boolean isEmpty() {
return N==0;
}
//4.获取第一个元素
public T getFirst() {
//判断链表是否为空
if (!isEmpty()) {
Node n = head;
return n.next.item;
}
return null;
}
//5.获取最后一个元素
public T getLast() {
if (!isEmpty()) {
return last.item;
}
return null;
}
//6.插入元素t 即在最后插入一个元素,创建一个过度元素,把最后一个节点的copy到这个过度元素,
//要新插入的元素放到last节点内
public void insert(T t) {
//分为当前链表为空与不为空的两种情况
if (isEmpty()) {
//为空
last = new Node(t,head,null); //让这个新结点成为尾结点,并且它的前指针指向头结点
head.next = last; //让头结点的后指针指向这个新结点
}
else{
//不为空
//之前的尾结点变为老的尾结点
Node oldLast = last;
//创建新结点,让它的前指针直向老的尾结点
Node newNode = new Node(t,oldLast,null);
//让老的尾结点直向新节点
oldLast.next = newNode;
//让新节点成为尾结点
last = newNode;
}
//元素个数加1
N++;
}
//6.在指定位置i处插入元素t
public void insert(int i,T t) {
//找到i-1位置的结点
Node n =head;
for (int index=0; index<=i-1; index++) {
n=n.next;
}
找到i位置的结点
Node curr = n.next;
//创建新结点,让i-1位置处的结点的后指针指向这个结点
Node newNode = new Node(t,n,curr);
n.next=newNode;
curr.pre=newNode;
//元素的个数加一
N++;
}
//7.获取指定位置i处的元素
public T get(int i) {
//找到i位置的结点
Node n =head;
for (int index=0; index<=i; index++) {
n=n.next;
}
return n.item;
}
//8.查找元素t在链表中第一次出现的位置
public int indexOf(T t) {
Node n =head;
for (int index=0; index iterator() {
return new IteratorImpl();
}
public class IteratorImpl implements Iterator {
//内部类IteratorImpl的成员变量
private Node n;
//构造方法
public IteratorImpl() {
this.n = head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next() {
n=n.next;
return n.item;
}
}
}