话不多说上代码
/**
* 双端链表
*/
public class DoublePointLinkedList<T> {
// 链表中的每一个节点
private class Node{
private T data; // 链表中的数据
private Node next; // 下一个节点
public Node(T data){
this.data = data;
}
}
private Node head; // 头节点
private Node tail; // 尾节点
private int size; // 链表长度
// 初始化
public DoublePointLinkedList(){
this.head = null;
this.tail = null;
this.size = 0;
}
// 在链表头新增节点
public boolean addHead(T data){
// 构建新节点
Node newNode = new Node(data);
// 如果当前链表为空 将头节点和尾节点都指向新增的节点
if(this.size == 0){
this.head = newNode;
this.tail = newNode;
}else{
// 将新创建节点的 next 节点指向 head 头节点
newNode.next = this.head;
// 再将 head 头节点指向 新创建节点
this.head = newNode;
}
this.size ++;
return true;
}
// 在链表的尾部新增节点
public boolean addTail(T data){
// 构建新节点
Node newNode = new Node(data);
// 如果链表为空，将头节点和尾节点都指向新增节点
if(this.size == 0){
this.head = newNode;
this.tail = newNode;
}else{
// 由于新增了尾节点链表的节点也必须增加
// 这里 tail 尾节点 和 head 头节点指向的是同一引用
// 这一将 tail 的 next 节点设置为 新创建节点
// 也就相当于在原来链表的基础上再尾部新增了一个节点
this.tail.next = newNode;
this.tail = newNode;
}
this.size ++;
return true;
}
// 删除头节点 成功返回 删除数据
public T removeHead(){
// 如果链表中没有数据
if(this.size == 0){
throw new RuntimeException("链表中没有数据");
}
// 获取头节点数据
T t = this.head.data;
// 如果链表中只有一条数据
// 将头节点和尾节点头清空
if(this.size == 1){
this.head = null;
this.tail = null;
}else{
// 将头节点 next 节点设置为 head 头节点
this.head = this.head.next;
}
size --;
return t;
}
// 删除尾节点
public T removeTail(){
// 如果链表中没有数据
if(this.size == 0){
throw new RuntimeException("链表中没有数据");
}
// 获取尾节点值
T t = tail.data;
// 如果链表中只有一条数据，将 head 集合 tail 都设置为 null
if(this.size == 1){
this.head = null;
this.tail = null;
}
Node curr = this.head; // 表示当前节点
Node prrvious = this.head; // 表示当前节点的上一个节点
// curr 的 next 节点入过不为空说明还没有到最有一个节点
// 反之已经是最后一个节点了
while (curr.next != null){
// 将当前节点的上一个节点指向当前节点
prrvious = curr;
// 将当前节点指向为当前节点的下一个节点，直到找到最后一个节点
curr = curr.next;
}
// 走到这里 curr 已经是最后一个节点了,也就是尾节点
// 删除尾节点,也就是将最后一个节点设置为 null
// 由于 curr 节点的上一个节点 previous 的 next 节点指向的 curr 节点就是最后一个节点
// 所以要将 previous 的 next 节点设置为 null
prrvious.next = null;
// 设置新的尾节点 将 tail 指向 curr 的上一个节点 previouts 即可
this.tail = prrvious;
size --;
return t;
}
// 打印节点信息
public void display(){
if(this.size > 0){
Node curr = this.head; // 头节点
int tempSize = this.size; // 链表长度
while (tempSize > 0){
// 头节点
if(curr.equals(this.head)){
System.out.print("["+curr.data+"->");
}else if(curr.next == null){
// 最有一个节点
System.out.print(curr.data+"]");
}else {
// 其他节点
System.out.print(curr.data+"->");
}
// 将当前节点指向到 当前节点的 next 下一个节点
// 直到找最有一个节点
curr = curr.next;
tempSize --;
}
System.out.println();
}else{
// 没有数打印空
System.out.println("[]");
}
}
public static void main(String[] args) {
DoublePointLinkedList<String> doublePointLinkedList = new DoublePointLinkedList<String>();
System.out.println("***************** 在尾部新增节点 *******************");
doublePointLinkedList.addTail("A");
doublePointLinkedList.addTail("B");
doublePointLinkedList.addTail("C");
doublePointLinkedList.addTail("D");
doublePointLinkedList.addTail("E");
// 打印数据
doublePointLinkedList.display();
// 新增头节点
System.out.println("***************** 在头部新增节点 *******************");
doublePointLinkedList.addHead("9");
doublePointLinkedList.addHead("8");
// 打印数据
doublePointLinkedList.display();
System.out.println("***************** 在尾部新增节点 *******************");
// 新增尾节点
doublePointLinkedList.addTail("F");
// 打印数据
doublePointLinkedList.display();
System.out.println("***************** 删除头节点 *******************");
// 删除头节点
doublePointLinkedList.removeHead();
// 打印数据
doublePointLinkedList.display();
System.out.println("***************** 删除尾节点 *******************");
// 删除尾节点
doublePointLinkedList.removeTail();
// 打印数据
doublePointLinkedList.display();
}
}
结果
***************** 在尾部新增节点 *******************
[A->B->C->D->E]
***************** 在头部新增节点 *******************
[8->9->A->B->C->D->E]
***************** 在尾部新增节点 *******************
[8->9->A->B->C->D->E->F]
***************** 删除头节点 *******************
删除的头节点=8
[9->A->B->C->D->E->F]
***************** 删除尾节点 *******************
删除的尾节点=F
[9->A->B->C->D->E]
网友评论