实现类
package day03;
/**
* @Author yqq
* @Date 2022/05/05 21:35
* @Version 1.0
* 模拟双链表
*/
public class DoubleLinkedList {
/**
* 用于保存双向链表首节点
*/
private Node headNode;
/**
* 用于保存双向链表的尾结点
*/
private Node lastNode;
/**
* 用于保存双向链表中节点的个数
*/
private int size;
/**
* 获取双向链表中的个数
* @return
*/
public int size(){
return this.size;
}
/**
* 添加元素
* @param element
*/
public void add(Object element){
//把需要添加的元素封装成一个节点对象
Node node = new Node(element);
//处理双向链表为空的情况
if (headNode == null){
//把node节点设置为头结点
headNode = node;
//把node节点设置为尾结点
lastNode = node;
}else {
//设置lastNode的next值为node
lastNode.next = node;
//设置node的pre值为lastNode
node.pre = lastNode;
//设置node节点为双链表节点的尾结点
lastNode = node;
}
//更新size的值
size ++;
}
/**
* 根据序号获得元素
* @param index
* @return
*/
public Object get(int index){
//判断序号是否合法,合法范围[0,size - 1]
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("序号不合法，index:" + index);
//根据序号获得对应节点对象
Node node = node(index);
//获得并返回node节点数据值
return node.data;
}
/**
* 根据序号删除元素
* @param index
*/
public void remove(int index){
//判断序号是否合理
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("序号不合法，index:" + index);
//处理删除节点为首节点的情况
if (index == 0){
//获得删除节点的下一个节点
Node nextNode = headNode.next;
//设置删除节点的值为null（首节点）
headNode.next = null;
//判断首节点是否也是尾节点,如果是，则双链表删除后为空链表
if (nextNode != null)
//设置nextNode节点pre为null
nextNode.pre = null;
//设置nextNode为双链表的首节点
headNode = nextNode;
}
//处理删除节点为尾节点的情况
else if (index == size - 1){
//获得删除节点的前一个节点
Node preNode = lastNode.pre;
//设置preNode的next为null
preNode.next = null;
//设置lastNode的pre为null
lastNode.pre = null;
//设置preNode为尾结点
lastNode = preNode;
}
//处理删除节点为中间任何节点的情况
else {
//获得删除节点对象
Node delNode = node(index);
//获得删除节点的前一个节点
Node preNode = delNode.pre;
//获得删除节点的后一个节点
Node nextNode = delNode.next;
//设置删除节点的前一个节点指向删除节点的后一个节点
preNode.next = nextNode;
//设置删除节点的后一个节点指向删除节点的前一个节点
nextNode.pre = preNode;
//设置删除节点的next和pre为null
delNode.pre = null;
delNode.next = null;
}
//更新size的值
size --;
}
/**
* 根据序号插入元素
* @param index
* @param element
*/
public void add(int index,Object element){
//判断序号是否合法，序号合法范围[0,size]
if (index < 0 || index > index)
throw new IndexOutOfBoundsException("序号不合法，index:" + index);
//把需要添加的数据封装成一个节点对象
Node node = new Node(element);
//处理插入节点在开头的情况
if (index == 0){
//设置node的next为headNode
node.next = headNode;
//设置headNode的preNode为node
headNode.pre = node;
//将node设置为双链表的首节点
headNode = node;
}
//处理插入节点在末尾的情况
else if (index == size){
//插入原理与add方法一样
add(element);
}
//处理插入节点在中间任意位置的情况
else {
//获得插入位置所对应的节点对象
Node curNode = node(index);
//获得插入位置节点的前一个节点
Node preNode = curNode.pre;
//设置node节点和preNode节点之间的连线
preNode.next = node;
node.pre = preNode;
//设置node节点和curNode节点之间的连线
node.next = curNode;
curNode.pre = node;
}
//更新size的值
size ++;
}
/**
* 根据序号获得对应的节点对象
* @param index
* @return
*/
private Node node(int index){
//如果查找的节点在双链表的前半区，则从前往后查找
if (index < size / 2){
//定义一个临时节点，用于辅助双链表的遍历
Node nextNode = headNode;
//定义一个循环从前往后查找index所对应节点
for (int i = 0; i < index; i++) {
nextNode = nextNode.next;
}
//返回index对应的节点
return nextNode;
}
//如果查找的节点在双链表的后半区，则从后往前查找
else {
//定义一个临时节点辅助双链表的遍历
Node preNode = lastNode;
//定义一个循环从后往前查找index对应节点对象
for (int i = size - 1; i > index; i--) {
//更新preNode的值
preNode = preNode.pre;
}
//返回index对应的节点对象
return preNode;
}
}
/**
* 节点类
*/
private static class Node{
/**
* 用于保存节点中的数据
*/
private Object data;
/**
* 用于保存上一个节点的地址值
*/
private Node pre;
/**
* 用于保存下一个节点的地址值
*/
private Node next;
public Node(Object data) {
this.data = data;
}
}
}
测试类
package day03;
/**
* @Author yqq
* @Date 2022/05/05 22:31
* @Version 1.0
*/
public class Test03 {
public static void main(String[] args) {
DoubleLinkedList list = new DoubleLinkedList();
list.add("11");
list.add("22");
list.add("33");
//根据序号删除元素
// list.remove(2);
//根据序号插入元素
list.add(3,"1");
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
// System.out.println(list.get(1));
}
}
