零、前言
链表是一种数据结构，用来承载数据，每个表节点装载一个数据元素
双链表是每个节点出来数据元素外还分别持有前、后两个节点的引用
为了统一节点的操作，一般在真实链表的首尾各加一个虚拟节点，称为头节点和尾节点
一、链表的操作
下图是一个三个节点的双链表
双链表.png
/**
* 作者：张风捷特烈
* 时间：2018/9/18 0018:7:35
* 邮箱：1981462002@qq.com
* 说明：双链表
*/
public class DoubleLink<T> {
/**
* 虚拟头结点
*/
private Node headNode;
/**
* 虚拟尾节点
*/
private Node tailNode;
/**
* 链表长度(节点数)
*/
private int size;
/**
* 节点类
* @param <T>
*/
private static class Node<T> {
/**
* 数据
*/
public T data;
/**
* 前节点
*/
public Node prev;
/**
* 后节点
*/
public Node next;
public Node(Node prev, Node next, T data) {
this.data = data;
this.prev = prev;
this.next = next;
}
}
}
1.插入操作：addBefore()
假如在第二个元素处插入，会发生什么： 1---新建一个node,将前、后指向分别指向目标前节点和目标节点 2---目标前节点next指向新节点 3---目标节点prev指向新节点 3---链表长度+1
双链表前插入.png
/**
* 根据目标节点插入新节点
* @param target 目标节点
* @param data 新节点数据
*/
private void addNodeBefore(Node<T> target, T data) {
//新建一个node,将前、后指向分别指向目标前节点和目标节点
Node<T> newNode = new Node<>(target.prev, target, data);
//目标前节点next指向新节点
target.prev.next = newNode;
//目标节点prev指向新节点
target.prev = newNode;
//链表长度+1
size++;
}
2.移除操作：removeNode()
假如在删除第二个元素，会发生什么： 1---目标前节点的next指向目标节点后节点 2---目标后节点的prev指向目标节点前节点
3---链表长度-1 4---返回删除的数据
双链表移除节点.png
/**
* 移除目标节点
*
* @param target 目标节点
* @return 目标节点数据
*/
private T removeNode(Node<T> target) {
//目标前节点的next指向目标节点后节点
target.prev.next = target.next;
//目标后节点的prev指向目标节点前节点
target.next.prev = target.prev;
//链表长度-1
size--;
return target.data;
}
3.清空操作：clearNode()
思路和删除一样：首尾虚拟节点互指，中间的元素就被孤立了，从而从链表上全部删除 1---实例化头结点 2---实例化尾节点，并将prev指向头 3---头结点的next指向尾节点 4---链表长度置零
双链表清空.png
/**
* 清空所有节点
*/
private void clearNode() {
//实例化头结点
headNode = new Node<T>(null, null, null);
//实例化尾节点，并将prev指向头
tailNode = new Node<T>(headNode, null, null);
headNode.next = tailNode;
//链表长度置零
size = 0;
}
4.获取操作：getNode
思路：链表查找只能一个一个挨着找，就像排队报数样。 为了尽量高效，判断一下索引在前半还是后半，来采取前报数，还是后报数。
/**
* 根据索引获取节点
*
* @param index 索引
* @return 索引处节点
*/
private Node<T> getNode(int index) {
//声明目标节点
Node<T> targetNode;
//索引越界处理
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException();
}
//如果索引在前半,前序查找
if (index < size / 2) {
targetNode = headNode.next;
for (int i = 0; i < index; i++) {
targetNode = targetNode.next;
}
} else { //如果索引在后半,反序查找
targetNode = tailNode.prev;
for (int i = size - 1; i < index; i++) {
targetNode = targetNode.prev;
}
}
return targetNode;
}
二、利用链表实现对数据的操作
链表只是对节点的操作，只是一种结构，并非真正目的，在集合类中要让链表对外完全不可见,就像人的骨骼之于躯体 躯体的任何动作是骨骼以支撑,而骨骼并不可见，从外来看只是躯体的动作而已，数据结构就是这样的骨架，数据便是躯体。 我们需要的是按照这种结构对数据进行增删改查等操作，并暴露接口由外方调用
1.普通集合操作：增删改查
public class DoubleLinkedGroup<T> extends Group<T> {
/**
* 虚拟头结点
*/
private Node headNode;
/**
* 虚拟尾节点
*/
private Node tailNode;
public DoubleLinkedGroup() {
clear();
}
@Override
public void add(int index, T el) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Illegal index");
}
addNodeBefore(getNode(index), el);
}
@Override
public T remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Remove failed. Illegal index");
}
return removeNode(getNode(index));
}
@Override
public void clear() {
clearNode();
}
@Override
public T set(int index, T el) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Set failed. Illegal index");
}
Node<T> node = getNode(index);
T oldData = node.el;
node.el = el;
return oldData;
}
@Override
public T get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Get failed. Illegal index");
}
return getNode(index).el;
}
@Override
public void addLast(T el) {
add(size, el);
}
}
2.普通方法测试：
private static void baseTest() {
DoubleLinkedGroup<String> list = new DoubleLinkedGroup<>();
//添加测试
list.addFirst("特");
list.addFirst("张");
list.add(1,"风");
list.add(2,"捷");
list.addLast("烈");
//输出测试
System.out.println(list);
//head: 张->风->捷->特->烈->null->
//移除测试
list.remove(3);
System.out.println(list);
//head: 张->风->捷->烈->null->
//修改测试
list.set(2,"神");
System.out.println(list);
//head: 张->风->神->烈->null->
//获取测试
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i));//张风神烈
}
//大小测试
System.out.println(list.size());//4
//是否为空测试
System.out.println(list.isEmpty());//false
//清空测试
list.clear();
System.out.println(list.isEmpty());//true
}
}
二、其他方法测试
定元素查询索引、删除 两个双链表式集合定点连接
1.代码实现
@Override
public int[] getIndex(T el) {
//临时数组
int[] tempArray = new int[size];
//重复个数
int index = 0;
int count = 0;
Node node = headNode.next;
while (node != null) {
if (el.equals(node.el)) {
tempArray[index] = -1;
count++;
}
index++;
node = node.next;
}
//将临时数组压缩
int[] indexArray = new int[count];
int indexCount = 0;
for (int i = 0; i < tempArray.length; i++) {
if (tempArray[i] == -1) {
indexArray[indexCount] = i;
indexCount++;
}
}
return indexArray;
}
@Override
public Group<T> contact(int index, Group<T> group) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Contact failed. Illegal index");
}
DoubleLinkedGroup linkedGroup = (DoubleLinkedGroup) group;
Node targetNode = getNode(index);
Node targetNextNode = targetNode.next;
//目标节点的next指向待接链表的第一个节点
targetNode.next = linkedGroup.getHeadNode().next;
//向待接链表的第一个节点的prev指向目标节点
linkedGroup.getHeadNode().next.prev = targetNode;
//目标节点的下一节点指的prev向待接链表的最后一个节点
targetNextNode.prev = linkedGroup.getTailNode().prev;
//向待接链表的最后一个节点的next指向目标节点的下一节点的
linkedGroup.getTailNode().prev.next = targetNextNode;
return this;
}
public Node getHeadNode() {
return headNode;
}
public Node getTailNode() {
return tailNode;
}
2.其他方法测试
/**
* 其他方法测试
*/
private static void otherTest() {
DoubleLinkedGroup<String> linkedGroup = new DoubleLinkedGroup<>();
linkedGroup.addLast("a");
linkedGroup.addLast("b");
linkedGroup.addLast("a");
linkedGroup.addLast("c");
linkedGroup.addLast("a");
System.out.println(linkedGroup);
//head: a->b->a->c->a->null->
//获取a元素的所有索引位置
int[] as = linkedGroup.getIndex("a");
for (int a : as) {
System.out.print(a + " ");//0 2 4
}
//删除a元素第一次出现的地方---
linkedGroup.removeEl("a");
System.out.println(linkedGroup);
//head: b->a->c->a->null->
//查看a元素是否存在
boolean b = linkedGroup.contains("a");
System.out.println(b);//true
//删除所有a元素出现的地方---
linkedGroup.removeEls("a");
System.out.println(linkedGroup);
//head: b->c->NULL
//双链表合并测试
DoubleLinkedGroup<String> linkedGroup2 = new DoubleLinkedGroup<>();
linkedGroup2.addLast("1");
linkedGroup2.addLast("3");
linkedGroup2.addLast("2");
linkedGroup.contact(0, linkedGroup2);
System.out.println(linkedGroup);
//head: b->1->3->2->c->null->
}
后记、
1.声明：
[1]本文由张风捷特烈原创,各图均由本人亲自所画，转载请注明
[2]欢迎广大编程爱好者共同交流 [3]个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正 [4]你的喜欢与支持将是我最大的动力
2.连接传送门：
更多数据结构知识欢迎访问:图解数据结构 项目源码均在我的github/DS：欢迎star 张风捷特烈个人网站，编程笔记请访问：http://www.toly1994.com
3.联系我
QQ:1981462002 邮箱：1981462002@qq.com 微信：zdl1994328
4.欢迎关注我的微信公众号，最新精彩文章，及时送达：
公众号.jpg
转载于:https://www.cnblogs.com/toly-top/p/9781868.html
相关资源：JAVA上百实例源码以及开源项目
