线性表-双向链表
public class twoWayLinkList<T> {
public int N;
public Node head;
public Node last;
public static void main(String[] args) {
twoWayLinkList<String> s = new twoWayLinkList<>();
s.insert("测试");
s.insert("测试2");
s.insert("测试3");
s.insert(2, "我");
System.out.println(s.getFirst());
System.out.println(s.get(2));
System.out.println(s.length());
}
//结点类
private class Node{
//数据
T item;
//指向结点
//上一个
Node pre;
//下一个
Node next;
public Node(T item, Node pre,Node next){
this.item = item;
this.pre = pre;
this.next = next;
}
}
//初始化
public twoWayLinkList(){
N = 0;
//无前驱和后继
head = new Node(null, null, null);
last = null;
}
//清除
public void clear(){
this.head.next = null;
this.last.pre = null;
N = 0;
}
//是否为空
public boolean isempty(){
return N==0;
}
//长度
public int length(){
return N;
}
//获取i位置处的元素t
public T get(int i){
Node n = head;
//找新节点的前一个结点
for (int index = 0; index < i; index++) {
n = n.next;
}
return n.item;
}
//获取第一个元素
public T getFirst(){
if(isempty()){
return null;
}
return head.next.item;
}
//获取最后一个元素
public T getLast(){
if(isempty()){
return null;
}
return last.item;
}
//插入
public void insert(T t){
//是否为空
if (isempty()){
Node newNode = new Node(t, head, null);
last = newNode;
head.next = last;
}else {
Node oldLast = last;
Node newNode = new Node(t, oldLast, null);
oldLast.next = newNode;
last = newNode;
}
N++;
}
//向i位置处插入元素t
public void insert(int i ,T t){
//默认不为空
Node n = head;
//找新节点的前一个结点
for (int index = 0; index < i-1; index++) {
n = n.next;
}
//原位置处的结点
Node originalNode = n.next;
//创建新结点
Node newNode = new Node(t, n, originalNode);
originalNode.pre = newNode;
n.next = newNode;
N++;
}
//删除并返回删除的元素
public T delete(int i){
//默认不为空
Node n = head;
//找新节点的前一个结点
for (int index = 0; index < i-1; index++) {
n = n.next;
}
return head.item;
}
}