链表是一种线性的数据结构 是一种最简单的动态数据结构
优点： 动态创建，节省空间
头部添加容易
缺点：空间上不连续，查找困难。只能从头开始一个一个找
对于单链表：
链表类Node的成员变量有：T类型的数据和Node类型的节点，并且成员变量node指向下一个节点。
为了统一节点的操作，通常在链表最前面添加一个虚拟头结点
链表.png
一个链表.png
我想再强调一下数据结构的作用是为数据寻找一个合适的载体，让数据的操作更加快捷。
Node只不过是一个辅助工具，并不会暴露在外。它与数据相对应，又使数据按链式排布，
操纵节点也就等于操纵数据，就像提线木偶，我们操作的是"观众"所看不见的线，而不是木偶的各个肢体本身。
一、单链表实现集合：SingleLinkedGroup
1.节点类的设计
/**
* 内部私有节点类
* @param <T>
*/
private class Node<T>{
/**
* 节点数据元素
*/
public T el;
/**
* 下一节点的引用
*/
public Node next;
public Node(T el, Node next) {
this.el = el;
this.next = next;
}
@Override
public String toString() {
return el.toString();
}
}
2.SingleLinkedGroup继承自Group 基类见第一篇
public class SingleLinkedGroup<T> extends Group<T> {
/**
* 虚拟头结点
*/
private Node headNode;
public SingleLinkedGroup() {
clear();
}
@Override
public void add(int index, T el) {
}
@Override
public T remove(int index) {
return null;
}
@Override
public void clear() {
headNode = new Node(null, null);
size = 0;
}
@Override
public T set(int index, T el) {
return null;
}
@Override
public T get(int index) {
return null;
}
@Override
public int[] getIndex(T el) {
return new int[0];
}
@Override
public Group<T> contact(int index, Group<T> group) {
return null;
}
/Node类见上方
}
二、底层节点操作
1.定点插入
1---新节点的next指向目标节点 2---目标节点的上一节点(即data1)的next指向新节点 3---增加size
添加节点.png
/**
* 在指定链表前添加节点
*
* @param index 索引
* @param el 数据
*/
private void addNode(int index, T el) {
Node<T> target = getNode(index - 1);
//新建节点，同时下一节点指向target的下一节点
Node<T> tNode = new Node<>(target.next, el);
//目标节点的next指向新节点
target.next = tNode;
size++;
}
2.定点获取
思路：链表查找只能一个一个挨着找，就像排队报数样。
/**
* 根据索引寻找节点
* @param index 索引
* @return 节点
*/
private Node<T> getNode(int index) {
//声明目标节点
Node<T> targetNode = headNode;
for (int i = 0; i < index; i++) {
//一个挨着一个找，直到index
targetNode = targetNode.next;
}
return targetNode;
}
3.定点修改
/**
* 修改节点
* @param index 节点位置
* @param el 数据
* @return 修改后的节点
*/
private Node<T> setNode(int index, T el) {
Node<T> node = getNode(index);
node.el = el;
return node;
}
4.定点移除
思路：目标节点的前一节点的next指向目标节点的下一节点(即把元素孤立) 把目标节点的next指向为null
链表移除节点.png
/**
* 移除指定索引的节点
*
* @param index 索引
* @return 删除的元素
*/
private T removeNode(int index) {
//目标节点前一节点
Node<T> targetPrev = getNode(index - 1);
//目标节点
Node<T> target = targetPrev.next;
//目标节点前一节点的next指向目标节点下一节点
targetPrev.next = target.next;
target.next = null;
size--;
return target.el;
}
三、集合类外部访问接口实现
1、增：添加--add
@Override
public void add(int index, T el) {
// index可以取到size，在链表末尾空位置添加元素。
if (index+1 < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Illegal index");
}
addNode(index + 1, el);
}
2.删:移除--remove
@Override
public T remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Remove failed. Illegal index");
}
return removeNode(index + 1);
}
3.该：修改--set
@Override
public T set(int index, T el) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Set failed. Illegal index");
}
return setNode(index + 1, el).el;
}
4.查：获取--get
@Override
public T get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Get failed. Illegal index");
}
//消除headNode影响，所以+1
return getNode(index + 1).el;
}
5.测试
SingleLinkedGroup<String> list = new SingleLinkedGroup<>();
list.addFirst("特");
list.addLast("烈");
list.addFirst("风");
list.addFirst("张");
list.add(2, "杰");
list.set(2, "捷");
System.out.println(list);
//head: 张->风->捷->特->烈->NULL
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i));//张风捷特烈
}
list.remove(2);
//head: 张->风->特->烈->NULL
System.out.println(list);
list.clear();
System.out.println(list);//head: NULL
四、其他操作
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;
}
2.定点连接两个链表式集合
@Override
public Group<T> contact(int index, Group<T> group) {
SingleLinkedGroup<T> linkedGroup = (SingleLinkedGroup<T>) group;
//获取待接入链表 头结点
Node firstNode = linkedGroup.getHeadNode().next;
//获取待接入链表 尾结点
Node lastNode = linkedGroup.getLastNode();
//获取目标节点
Node<T> target = getNode(index+1);
//获取目标节点的下一节点
Node targetNext = target.next;
//获取目标节点的next连到 接入链表 头结点
target.next = firstNode;
//待接入链表 尾结点连到 目标节点的下一节点
lastNode.next = targetNext;
return this;
}
public Node getHeadNode() {
return headNode;
}
public Node getLastNode() {
return getNode(size);
}
2.其他方法测试:
SingleLinkedGroup<String> linkedGroup = new SingleLinkedGroup<>();
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
SingleLinkedGroup<String> linkedGroup2 = new SingleLinkedGroup<>();
linkedGroup2.addLast("1");
linkedGroup2.addLast("3");
linkedGroup2.addLast("2");
linkedGroup.contact(1, linkedGroup2);
System.out.println(linkedGroup);
//head: b->c->1->3->2->NULL
五、时间测试：单链表式集合：SingleLinkedGroup测试
方法\数量复杂度10001000010W100W1000W
addLastO(n)0.0029秒0.1096秒9.1836秒--------addFirstO(1)0.0002秒0.0009秒0.0036秒0.5039秒3.1596秒addO(n)----------removeLastO(n)0.0012秒0.1009秒8.9750秒--------removeFirstO(1)0.0001秒0.0016秒0.0026秒0.0299秒0.1993秒removeElO(n)----------removeElsO(n)----------removeO(n)----------clearO(1)----------setO(n)----------getO(n)----------getIndexO(n)----------
后记、
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/9781869.html
相关资源：JAVA上百实例源码以及开源项目
