一前言
出于好奇发了点时间实现了一个简单的单向链表，本篇之中是使用单方向的方式实现，感觉不是很满意，有空应该研究一下头和尾的实现方式；数据结构有点弱，研究起来挺头疼，市面上也没有较好的书籍；
二 链表介绍
Java中ArrayList就是单向链表的实现方式（有研究过源码的读者肯定发行了ArrayList的链表实现方式是依赖于数组实现的），单向链表的查找比较慢，但是增删却很快；链表的每个节点（称为Node）都存储有一个数据（data）和下一个节点的指针（本文称为next）；链表的尾节点指向null；
三 链表的实现
3.1 定义节点
节点中定义了data储存数据，方便实现使用了整型；Node类中还定义了下一个节点的指针；这样就简单实现了一个链表，前一个节点中就存储着下一个节点的引用；
/**
* @Author lsc
* <p> 链表节点</p>
*/
public class Node {
// 表示储存数据
public Integer data;
// 表示指向下一个Node的指针
public Node next;
// 构造函数
Node(){
}
Node(Integer data){
this.data = data;
}
}
3.2 添加节点
思路 ： 就是在链表的尾节点添加数据作为链表新的尾节点
/**
* @Author lsc
* <p> 单链表实现 </p>
*/
public class ZList {
// 链表头
Node head = null;
/* *
* @Author lsc
* <p> 思路就是在链表的尾节点添加数据作为链表新的尾节点</p>
* @Param [data]
* @Return void
*/
public void add(int data){
// 创建新的节点
Node newNode = new Node(data);
// 如果头节点为空，将新节点作为头节点
if (head==null){
head = newNode;
}else {
// 创建临当前节点，每次添加都需要从头开始寻找尾节点
Node currentNode = head;
// 循环遍历 查找尾节点
while (currentNode.next!=null){
currentNode = currentNode.next;
}
// 此时 currentNode 存储的是尾节点，需要在尾节点添加新节点作为新的尾节点
currentNode.next = newNode;
}
}
/* *
* @Author lsc
* <p> 思路:遍历链表 </p>
* @Param []
* @Return void
*/
public void recursive(){
// 表示当前节点
Node currentNode = head;
while (currentNode!=null){
// 打印当前节点内容
System.out.println(currentNode.data);
// 将下一个节点作为当前节点
currentNode = currentNode.next;
}
}
}
测试
public static void main(String[] args) {
ZList zList = new ZList();
for (int i = 0; i <5 ; i++) {
zList.add(i);
}
zList.recursive();
}
输出
0
1
2
3
4
3.3 获得链表长度
思路:链表的长度就是Node的个数
/* *
* @Author lsc
* <p> 思路:链表的长度就是Node的个数 </p>
* @Param []
* @Return int
*/
public int size(){
// 定义长度
int length = 0;
// 创建临时节点
Node currentNode = head;
// 遍历获得长度
while (currentNode!=null){
// 将下一个节点作为当前节点
currentNode = currentNode.next;
// 长度加1
length++;
}
return length;
}
3.4 指定位置添加节点
如下图所示，指定位置添加节点，需要将原来的节点指向新的节点，新节点指向原来节点的下一个节点；这边最重要的一点就是插入数据的位置是从第二个节点后面插入新节点（比如插入数据的索引是3，那么插入的位置应该是2的后面，找的位置也就是2）；
/* *
* @Author lsc
* <p> 指定位置插入数据
* 思路：假设要在Z和X位置插入，则需将Z指向新节点，新节点指向X
* ZSZXZ --> ZSZ@XZ
* 找位置很重要，也就是当前节点的上一个位置
* </p>
* @Param [data, index]
* @Return void
*/
public void add(int data, int index){
if (index<0 || index>size()){
System.out.println("非法索引");
return;
}
// 当前节点
Node currentNode = head;
int point = 0;
// 创建新的节点
Node newNode = new Node(data);
// 临时节点
Node tem;
while (currentNode.next!=null){
// 上一个位置，进入添加操作,否则继续遍历
if ((index-1)==point){
// 转存当前节点的下一个节点
tem = currentNode.next;
// 当前节点的指针next指向新节点
currentNode.next = newNode;
// 新节点的指针next指向当前节点的下一个节点
newNode.next = tem;
return;
}else {
currentNode = currentNode.next;
// node前进一次，指针加1
point++;
}
}
}
测试
public static void main(String[] args) {
ZList zList = new ZList();
for (int i = 0; i <5 ; i++) {
zList.add(i);
}
zList.add(66,3);
zList.recursive();
}
输出
0
1
2
66
3
4
3.5 删除头节点
思路：将头节点下一个节点作为新的头节点
/* *
* @Author lsc
* <p> 思路: 将头节点下一个节点作为新的头节点 </p>
* @Param []
* @Return void
*/
public void removeFirst(){
Node currentNode = head;
if (currentNode!=null){
// 将头节点下一个节点作为新的头节点
head = currentNode.next;
}
}
测试
public static void main(String[] args) {
ZList zList = new ZList();
for (int i = 0; i <5 ; i++) {
zList.add(i);
}
zList.removeFirst();
zList.recursive();
}
输出
1
2
3
4
3.6 指定位置删节点
如下图所示，想要删除链表节点，只需要将想要删除的节点的前节点指针next指向想要删除节点的后一个节点；
比较重要的也是位置，比如知识追寻者想删除节点的位置是3，那么查找的时候也就是寻找节点2指向节点4，故节点2的位置是重点；
/* *
* @Author lsc
* <p> 思路：将想要删除节点的前一个节点指向想要删除节点的下一个节点
* 找位置很重要，也就是当前节点的上一个位置
* </p>
* @Param [index]
* @Return void
*/
public void remove(int index){
if (index<0 || index>size()){
System.out.println("非法索引");
return;
}
// 当前节点
Node currentNode = head;
int point = 0;
while (currentNode.next!=null){
// 上一个位置
if ((index-1)==point){
// 将当前一个节点的指针next指向想要删除节点的下一个节点
currentNode.next = currentNode.next.next;
return;
}else {
currentNode = currentNode.next;
// node前进一次，指针加1
point++;
}
}
}
3.7 删除尾节点
思路：将新的尾节点（倒数第二个节点的next）指向null
/* *
* @Author lsc
* <p> 思路：将新的尾节点指向null </p>
* @Param []
* @Return void
*/
public void removeLast(){
// 当前节点
Node currentNode = head;
// 寻找尾节点
while (currentNode.next!=null){
// 将下一个节点储存为想要删除的节点
Node deleteNode = currentNode.next;
// 将下一个节点作为当前节点
currentNode = currentNode.next;
// currentNode.next 将作为新的尾节点
if (currentNode.next.next==null){
// 尾节点指向null
deleteNode.next = currentNode.next.next;
return;
}
}
}
3.8 链表反转
最容易实现链表的反转方式就是使用栈；下面这种循环实现方式比较原生，不是很好理解,需要将每个节点反转；
Node reverse() {
// 当 head为空直接返回
if (head == null || head.next == null){
return head;
}
// 当前节点
Node currentNode = head;
// 前驱节点
Node preNode = null;
// 后续节点
Node nextNode = null;
while (currentNode != null){
// 保存下一个节点(即要反转的节点s)
nextNode = currentNode.next;
// 重置下一个节点(要反转的节点指向已经反转的节点，第一次为null)
currentNode.next = preNode;
// 保存当前节点为前驱节点(已经反转z)
preNode = currentNode;
// 将下一个节点作为当前节点,直至链表尾部(s)
currentNode = nextNode;
}
// 重新赋值给head
head = preNode;
return preNode;
}
测试
public static void main(String[] args) {
ZList zList = new ZList();
for (int i = 0; i <5 ; i++) {
zList.add(i);
}
zList.reverse();
zList.recursive();
}
输出
4
3
2
1
0