Java单向链表及源码解析
- **链表是通过逻辑储存的方式通过节点的引用来获取元素值，每个节点包含两个部分 首先第一部分是value元素值。 第二部分是next来获取下个节点的地址，通过next来串联各个地址获取其中的value元素 有序数组如果想要新增或者删减元素需要从头开始遍历逐个进行覆盖确保有序数组中的有序,时间复杂度为O(m*n)。 链表的复杂度相对有序数组要方便他的时间复杂度分别是O(1)和O(N)。 **
创建一个ILindkedList接口创建方法(模拟实现链表方法)
import java.util.List;
public interface ILinkedList {
//首位置新增元素
public void addFirst(int data);
//最后位置新增元素
public void addLast(int data);
//在指定位置新增元素
public void addIndex(int index,int data);
//在链表中删除key元素
public void remove(int key);
//删除所有key的元素
public void removeAll(int key);
//打印链表元素
public void display();
public void display(MyLinkedList.NodeList newhead);
//是否包含data
public boolean contains(int data);
//获取链表中元素的大小
public int size();
//清空链表
void clean();
//反转链表元素
public MyLinkedList.NodeList reverse();
//求中间节点以及后续节点元素
public MyLinkedList.NodeListmiddleNode(MyLinkedList.NodeList nodeList);
//求倒数自定义的n个的节点
public MyLinkedList.NodeList findKthToTail(int k);
public MyLinkedList.NodeList add(int data1,int data2,int data3,int data4);
//合并两个有序的链表
}创建MyLinkedList来实现接口的方法
import javax.xml.soap.Node;
public class MyLinkedList implements ILinkedList{
//创建一个static内部类来初始化节点属性
static class NodeList{
//元素值
public int value;
//节点指向的下一个地址
public NodeList next;
//构造方法只给value通过这个值来next下一个节点
public NodeList(int value) {
this.value = value;
}
}创建链表节点
//这里可以尝试创建一个链表
public void createLinkedList(){
NodeList node1=new NodeList(23);
NodeList node2=new NodeList(25);
NodeList node3=new NodeList(38);
NodeList node4=new NodeList(55);
//通过获取的对象来访问next链接下一个节点实现链接
node1.next=node2;
node2.next=node3;
node3.next=node4;
//这里node4的next节点为空值
//head作为头部来访问各个节点
this.head=node1;
}addFirst方法（新增头部属性）
@Override
public void addFirst(int data) {
//增加一个元素到链表中,增加到头部
//将data元素放入到类中
NodeList node=new NodeList(data);
NodeList cur=this.head;
//这里node.next来获取头部地址
node.next=head;
//将node赋给head
head=node;
}addLast方法（新增到末尾一个属性）
@Override
public void addLast(int data) {
//增加一个元素到末尾
NodeList node=new NodeList(data);
NodeList cur=this.head;
//这里我们查找最后一个位置的next节点是否为null，如果是null；
while(cur.next!=null){
cur = cur.next;
}
//循环出来cur.next的节点为null
cur.next=node;
}remove方法（删除指定属性）
@Override
public void remove(int key) {
//删除指定元素的next地址节点
if(this.head==null){
return;
}
//判断第一个值是否是key
if(this.head.data==key){
this.head=this.head.next;
}
//得到前缀
NodeList cur = findRemoveKey(key);
//判断返回值是否是空的
if(cur==null){
System.out.println("未找到该元素"+key);
return;
}
//将cur.next给到dele得到节点
NodeList dele=cur.next;
//将后一个节点的next给到cur.next从而指向其他节点dele原有节点消失
cur.next=dele.next;
}
private NodeList findRemoveKey(int key){
NodeList cur=this.head;
//cur.next不等于null数值
while(cur.next!=null){
if(cur.next.value==key){
return cur;
}
//cur.next节点获取下一个cur
cur = cur.next;
}
return null;
}removeAll（删除所有指定元素）
@Override
public void removeAll(int key) {
if(this.head==null){
return;
}
NodeList pre=this.head;
NodeList cur=pre.next;
//cur！=null说明有数据
while(cur!=null){
//value值为key进入循环
if(cur.value==key){
//pre的下个节点为cur的下一个节点，取消掉cur=key这个节点的链接
pre.next=cur.next;
cur=cur.next;
}else{
//如果不等于pre要跳到cur的位置来继续作为前一项
pre=cur;
//cur获取下一项
cur=cur.next;
}
}
//不要忽略头部，如果是key要替换掉
if(this.head.value==key){
this.head=this.head.next;
}
}addIndex方法（任意位置添加一个元素属性）
@Override
public void addIndex(int index, int data)throws ErrorRuntimeExcepetion {
//给一个位置，放入data元素
//如果index的值小于0或者大于本身长度抛出异常显示下标
try {
if(index<0||index>size()){
throw new ErrorRuntimeExcepetion("范围不准确"+index);
}
}catch (ErrorRuntimeExcepetion e){
e.printStackTrace();
return;
}
//如果index的位置是0或者index的位置是最后一个
if(index==0){
addFirst(data);
}
if(index==size()){
addLast(data);
}
//走到这里index的值为其范围内容，首先获取index-1的位置
NodeList cur = searchPre(index);
//生成data元素链表
NodeList node=new NodeList(data);
if(cur==null){
return;
}
//将原来cur.index的地址赋值给node.index来后移
node.next=cur.next;
//将现在的cur.index的地址指向node
cur.next=node;
}
private NodeList searchPre(int index){
NodeList cur=this.head;
//求一个index-1的范围
int count=0;
while(count<index-1){
cur=cur.next;
count++;
}
//获取到index-1位置的cur
return cur;
}display打印
@Override
public void display() {
//创建一个对象接收head值，来进行打印
NodeList cur=this.head;
//cur不等于null
while(cur!=null){
//通过cur引用value来打印元素
System.out.print(cur.value+" ");
//通过next中下一个节点的地址来访问元素
cur=cur.next;
}
System.out.println();
}contains（中包含某个元素）
@Override
public boolean contains(int data) {
//链表中是否包含data
NodeList cur=this.head;
if(cur.value==data){
//如果value是data返回true
return true;
}else{
while(cur.next!=null){
//循环每个节点判断是否为data
if(cur.next.value==data){
return true;
}
cur=cur.next;
}
}
return false;
}size（获取节点元素的数量）
@Override
public int size() {
//获取链表的元素大小
NodeList cur = this.head;
//如果cur中为null没有任何元素大小是0
if (cur == null) {
return 0;
}
int count=0;//计数
while(cur!=null){
count++;
cur=cur.next;
}
return count;
}clean（清空）
@Override
public void clean() {
if(this.head==null){
return;
}
//将每个节点置为空属性并且回收
NodeList cur=this.head;
while(cur!=null){
NodeList curNext=cur.next;
cur.next=null;
cur=curNext;
}
//置空null
this.head=null;
}求Middle位置（中间以及后续的节点属性）
方法1
@Override
public NodeList middleNode() {
if(this.head ==null){
return null;
}
if(this.head.next==null){
return this.head;
}
int size=size();
int middle=size/2;//记入中间值
int count=0;
NodeList cur=head;
while(count<middle){
cur=cur.next;
count++;//走一步加一次
}
return cur;
}方法2:
@Override
public NodeList middleNode(NodeList nodeList) {
if(nodeList==null){
return null;
}
if(nodeList.next==null){
return nodeList;
}
NodeList slow=nodeList;//设置一个slow每次走一个节点
NodeList fast=nodeList;//设置一个fast每次走两个节点
//当fast走完slow停在的位置就是中间我们要找的值
while(fast!=null&&fast.next!=null){
//以fast为起点因为fast首先走完
fast=fast.next.next;
slow=slow.next;
}
return slow;
}findkthToTail（求倒数第n个节点）
@Override
public NodeList findKthToTail(int k) {
if(k<=0||this.head==null){
return null;
}
NodeList fast=this.head;
NodeList slow=this.head;
while(k-1!=0){
fast=fast.next;
//fast如果走到null位置说明超出范围
if(fast==null){
return null;
}
k--;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}reverse(反转节点元素)upAndDown
@Override
public NodeList reverse() {
if(this.head==null){
return null;
}
if(this.head.next==null){
return head;
}
//得到head下一个节点的位置
NodeList cur=this.head.next;
//将head的下个节点置为空
this.head.next=null;
while(cur!=null){
//接收保留cur.next的节点方便后续使用
NodeList curNext=cur.next;
//将cur的下个节点置为head
cur.next=this.head;
//head切换为头部
this.head=cur;
//得到保留过的节点
cur=curNext;
}
return this.head;
}MyLinkedList类代码如下：
import javax.xml.soap.Node;
public class MyLinkedList implements ILinkedList{
//创建一个static内部类来初始化节点属性
static class NodeList{
//元素值
public int value;
//节点指向的下一个地址
public NodeList next;
//构造方法只给value通过这个值来next下一个节点
public NodeList(int value) {
this.value = value;
}
}
//创建一个带头链表来获取当前的节点第一个元素
public NodeList head;
//这里可以尝试创建一个链表
public void createLinkedList(){
NodeList node1=new NodeList(23);
NodeList node2=new NodeList(25);
NodeList node3=new NodeList(38);
NodeList node4=new NodeList(55);
//通过获取的对象来访问next链接下一个节点实现链接
node1.next=node2;
node2.next=node3;
node3.next=node4;
//这里node4的next节点为空值
//head作为头部来访问各个节点
this.head=node1;
}
@Override
public void addFirst(int data) {
//增加一个元素到链表中,增加到头部
//将data元素放入到类中
NodeList node=new NodeList(data);
if(this.head==null){
this.head=node;
}else {
//这里node.next来获取头部地址
node.next = this.head;
//将node赋给head
this.head = node;
}
}
@Override
public void addLast(int data) {
//增加一个元素到末尾
NodeList node=new NodeList(data);
NodeList cur=this.head;
//这里我们查找最后一个位置的next节点是否为null，如果是null；
while(cur.next!=null){
cur = cur.next;
}
//循环出来cur.next的节点为null
cur.next=node;
}
@Override
public void remove(int key) {
//删除指定元素的next地址节点
if(this.head==null){
return;
}
//得到前缀
NodeList cur = findRemoveKey(key);
//判断返回值是否是空的
if(cur==null){
System.out.println("未找到该元素"+key);
return;
}
//将cur.next给到dele得到节点
NodeList dele=cur.next;
//将后一个节点的next给到cur.next从而指向其他节点dele原有节点消失
cur.next=dele.next;
}
private NodeList findRemoveKey(int key){
NodeList cur=this.head;
//cur.next不等于null数值
while(cur.next!=null){
if(cur.next.value==key){
return cur;
}
//cur.next节点获取下一个cur
cur = cur.next;
}
return null;
}
@Override
public void removeAll(int key) {
if(this.head==null){
return;
}
NodeList pre=this.head;
NodeList cur=pre.next;
//cur！=null说明有数据
while(cur!=null){
//value值为key进入循环
if(cur.value==key){
//pre的下个节点为cur的下一个节点，取消掉cur=key这个节点的链接
pre.next=cur.next;
cur=cur.next;
}else{
//如果不等于pre要跳到cur的位置来继续作为前一项
pre=cur;
//cur获取下一项
cur=cur.next;
}
}
//不要忽略头部，如果是key要替换掉
if(this.head.value==key){
this.head=this.head.next;
}
}
@Override
public void addIndex(int index, int data)throws ErrorRuntimeExcepetion {
//给一个位置，放入data元素
//如果index的值小于0或者大于本身长度抛出异常显示下标
try {
if(index<0||index>size()){
throw new ErrorRuntimeExcepetion("范围不准确"+index);
}
}catch (ErrorRuntimeExcepetion e){
e.printStackTrace();
return;
}
//如果index的位置是0或者index的位置是最后一个
if(index==0){
addFirst(data);
}
if(index==size()){
addLast(data);
}
//走到这里index的值为其范围内容，首先获取index-1的位置
NodeList cur = searchPre(index);
//生成data元素链表
NodeList node=new NodeList(data);
if(cur==null){
return;
}
//将原来cur.index的地址赋值给node.index来后移
node.next=cur.next;
//将现在的cur.index的地址指向node
cur.next=node;
}
private NodeList searchPre(int index){
NodeList cur=this.head;
//求一个index-1的范围
int count=0;
while(count<index-1){
cur=cur.next;
count++;
}
//获取到index-1位置的cur
return cur;
}
@Override
public void display() {
//创建一个对象接收head值，来进行打印
NodeList cur=this.head;
//cur不等于null
while(cur!=null){
//通过cur引用value来打印元素
System.out.print(cur.value+" ");
//通过next中下一个节点的地址来访问元素
cur=cur.next;
}
System.out.println();
}
//从指定的链表开始遍历
@Override
public void display(NodeList newhead) {
NodeList cur=newhead;
while(cur!=null){
System.out.print(cur.value+" ");
cur=cur.next;
}
System.out.println();
}
@Override
public boolean contains(int data) {
//链表中是否包含data
NodeList cur=this.head;
if(cur.value==data){
//如果value是data返回true
return true;
}else{
while(cur.next!=null){
//循环每个节点判断是否为data
if(cur.next.value==data){
return true;
}
cur=cur.next;
}
}
return false;
}
@Override
public int size() {
//获取链表的元素大小
NodeList cur = this.head;
//如果cur中为null没有任何元素大小是0
if (cur == null) {
return 0;
}
int count=0;//计数
while(cur!=null){
count++;
cur=cur.next;
}
return count;
}
@Override
public void clean() {
if(this.head==null){
return;
}
//将每个节点置为空属性并且回收
NodeList cur=this.head;
while(cur!=null){
NodeList curNext=cur.next;
cur.next=null;
cur=curNext;
}
//置空null
this.head=null;
}
@Override
public NodeList reverse() {
if(this.head==null){
return null;
}
if(this.head.next==null){
return head;
}
//得到head下一个节点的位置
NodeList cur=this.head.next;
//将head的下个节点置为空
this.head.next=null;
while(cur!=null){
//接收保留cur.next的节点方便后续使用
NodeList curNext=cur.next;
//将cur的下个节点置为head
cur.next=this.head;
//head切换为头部
this.head=cur;
//得到保留过的节点
cur=curNext;
}
return this.head;
}
// @Override
// public NodeList middleNode() {
// if(this.head ==null){
// return null;
// }
// if(this.head.next==null){
// return this.head;
// }
// int size=size();
// int middle=size/2;//记入中间值
// int count=0;
// NodeList cur=head;
// while(count<middle){
// cur=cur.next;
// count++;//走一步加一次
// }
// return cur;
// }
@Override
public NodeList middleNode(NodeList nodeList) {
if(nodeList==null){
return null;
}
if(nodeList.next==null){
return nodeList;
}
NodeList slow=nodeList;//设置一个slow每次走一个节点
NodeList fast=nodeList;//设置一个fast每次走两个节点
//当fast走完slow停在的位置就是中间我们要找的值
while(fast!=null&&fast.next!=null){
//以fast为起点因为fast首先走完
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
@Override
public NodeList findKthToTail(int k) {
if(k<=0||this.head==null){
return null;
}
NodeList fast=this.head;
NodeList slow=this.head;
while(k-1!=0){
fast=fast.next;
//fast如果走到null位置说明超出k范围
if(fast==null){
return null;
}
k--;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}Test类代码：
public class Test {
public static void main(String[] args) {
MyLinkedList myLinkedList=new MyLinkedList();//这里创建链表对象
// myLinkedList.createLinkedList();//访问创建的链表
myLinkedList.addFirst(1);
myLinkedList.addFirst(12);
myLinkedList.addLast(13);
myLinkedList.addLast(14);
myLinkedList.addIndex(3,39);
myLinkedList.addIndex(5,10);
System.out.println(myLinkedList.contains(39));
myLinkedList.display();
// myLinkedList.remove(39);
// myLinkedList.removeAll(10);
// myLinkedList.display();
// myLinkedList.clean();
myLinkedList.addFirst(1);
myLinkedList.display();
MyLinkedList.NodeList node= myLinkedList.reverse();
myLinkedList.display(node);
MyLinkedList.NodeList middle=myLinkedList.middleNode(node);
myLinkedList.display(middle);
MyLinkedList.NodeList end = myLinkedList.findKthToTail(3);
myLinkedList.display(end);
MyLinkedList.NodeList a =myLinkedList.add(1,6,10,11);
MyLinkedList.NodeList Node2=myLinkedList.add(3,5,7,9);
System.out.println("链表中的元素大小为"+myLinkedList.size());
}
}#运行结果
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-11-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号