Java链表的基本介绍 java链表详解

使用JAVA做可爱得小单向链表，通过上线去找下线，上线莫名死了就完了，下线失联了，对下线得操作都要通过上线
1.使用类创造一个节点
2.建立一个头节点，头节点得地址就是整个链表得地址

JAVA中一个基本的链表节点就是这样的

public class HeroNode {//用类来做节点，一个节点就做完了

public int age;

public String name;

public String nickName;

public HeroNode next;//使用类做指针，指向下一个

@Override

public String toString() {//为了显示方便重写toString方法

return "HeroNode{" +

"age=" + age +

", name='" + name + '\'' +

", nickName='" + nickName + '\'' +

'}';

}

public HeroNode(){//一个无参构造

}

public HeroNode(int age, String name, String nickName){//一个构造器

this.age = age;

this.name = name;

this.nickName = nickName;

}

}

链表的内容和操作

public class SingleLInkedList {

private HeroNode headNode = new HeroNode();//头节点,头节点相当于变量地址

/*

<整理资料>

Q：什么是头结点？

A：数据结构中，在单链表的开始结点之前附设一个类型相同的结点，称之为头结点。头结点的数据域可以不存储任何信息，

头结点的指针域存储指向开始结点的指针（即第一个元素结点的存储位置）。

A：头结点其实就是一个数据域为空的结点（当然也可储存链表的长度之类的数据，一般对链表操作无影响），

而首元结点就是第一个元素结点，即头结点后边的第一个结点。

Q：用来干嘛？

A：

1、防止单链表是空的而设的。当链表为空的时候,带头结点的头指针就指向头结点。如果当链表为空的时候,

单链表没有带头结点,那么它的头指针就为NULL。

2、在第一个元素结点前插入结点（或删除第一个结点），使其操作与对其它结点一致。带头结点时，

不论删除哪个位置上的结点，用到的代码都一样；不带头结点时，删除第1个元素和删除其它位置上的元素用到的代码不同，

相对比较麻烦。

*/

public HeroNode getHeadNode() {

return headNode;

}

public void delete(int age){//删除节点，找到前一个节点

//根据年龄删除人

//辅助节点

HeroNode temp = headNode;

boolean flag = false;//判断有没有找到

while(true){

if(temp.next == null){

break;

}

if(temp.next.age == age){//找到位置了

flag = true;

break;

}

temp = temp.next;//没找到就继续往下走

}

if(flag){

temp.next = temp.next.next;

}

else

System.out.println("我们没找到");

}

//添加节点到单向列表

//找到当前链表，最后一个节点

//将next指向最后一个节点

public void add(HeroNode heroNode){

HeroNode temp = headNode;//一个头指针

while(true){//从头指针开始遍历

if(temp.next == null ){

break;

}

else

temp = temp.next;

//由于没有尾指针的概念，所以JAVA中链表，都是从头开始遍历，去找尾指针的

}

//将尾指针和后面连接起来

temp.next = heroNode;

}

public void show(){//显示链表

//需要辅助变量来遍历整个链表

//先判断链表是否为空

if(headNode == null){

System.out.println("链表为空你个傻逼");

}

else{

HeroNode temp = headNode.next;//从头节点的尾巴开始遍历

while(temp != null){

System.out.println(temp);//这里已经重写了toString方法

temp = temp.next;//指针后移

}

}

}

/*

添加一个变量进来，先找到变量添加位置的前一个节点，

断开添加位置的连接

然后插入完成

*/

public void insert(HeroNode heroNode){

HeroNode temp = headNode;

while(true){//寻找插入的位置

if(temp.next == null){

break;

}

if (temp.next.age > heroNode.age){//位置找到了，找到正确添加排名的位置了

break;//

}

else if(temp.next.age == heroNode.age){//说明要插入的位置查重复了

System.out.println("你插入重复了");

break;

}

temp = temp.next;

}

heroNode.next = temp.next;//给插上，先把尾巴接好，再去接头，接头接活过来了

temp.next = heroNode;

}

//根据年龄来对人物进行姓名和昵称的修改，对链表进行增删改查

public void update(HeroNode newHeroNode){

if(headNode.next == null){//先进行判空

System.out.println("链表为空");

return;

}

HeroNode temp = headNode;//熟悉的从头节点开始遍历的环节

//按照年龄找到需要修改的节点

boolean flag = false;

while(true){

if(temp == null){

break;//到链表的最后啦，我没找到

}

if (newHeroNode.age == newHeroNode.age){

flag = true;//这个要放在break之前,说明我找到了，而不是没找到

break; //说明你找到

}

}

if(flag){

temp.name = newHeroNode.name;

temp.nickName = newHeroNode.nickName;

}

else

System.out.println("没有找到这个编号，你是不是傻了");

}

}

面试题目

public class TencentGroup {

//面试第一题，求单链表的有效节点个数

public static int length(HeroNode headNode){//把头节点当地址传递进来

if(headNode.next == null){

System.out.println("这是空的单链表");

return 0;

}

int length = 0;

HeroNode temp = headNode.next;//辅助节点进行遍历,头节点不算，从第二个开始

while(true){

if(temp == null){

break;

}

else{

length ++;

}

temp = temp.next;

}

return length;

}

/*

查找倒数第k个节点

*/

public static HeroNode findKNode(int index,HeroNode headNode){//index查找倒数第几个节点

/*

先从头到尾遍历链表，得到链表总的长度，得到链表的有效节点后

从链表的头开始遍历

遍历到第n - k个节点

*/

if (headNode.next == null){

return null;

}

int length = TencentGroup.length(headNode);//直接调用写好了方法得到链表有效节点上个数

//先做一个Index的检验

if(index <= 0 || index > length){

System.out.println("目录有问题");

}

HeroNode temp = headNode.next;//用于去遍历

for (int i = 1; i <= length - index;i++ ){

if(temp == null){//遍历到头的话，跳出遍历

break;

}

temp = temp.next;

//一直找到倒数第k个节点

}

return temp;//将找到的节点返回去

}

}

/* 将链表反转 链表只能通过上面找下面 上线找下线 遍历链表 将遍历到的节点放在，新的头节点上，然后用头插法，把后面节点插上去 完成链表的改造 */

如图所示

单链表只能从上线找下线，下线没办法找上线
因此，遍历链表，采用头插法，将链表颠倒后放在新的头结点上

public HeroNode reversetList(HeroNode headNode){

System.out.println("传进来的地址是" + headNode);

/*

若只有一个节点直接返回

*/

if(headNode.next == null){

System.out.println("你个傻逼，没有");

}

else{

HeroNode temp = headNode.next;

HeroNode cur = null;//需要两个链表来控制移动节点

//一个移动上线，另一个保存下线，不然上线没了，下线找不到了

do{

cur = temp.next;//先保存，然后判断

//cur保存temp的下一个节点

temp.next = newHeadNode.next;//断开连接，头插法先把尾巴连接好

newHeadNode.next = temp;//与新的头节点连接上

temp = cur;//头指针移动去找下一个节

}

while(temp != null);

headNode.next = null;//最后让headNode链表归于平静

}

System.out.println("新头地址是" + newHeadNode);

return newHeadNode;

}

*我自己写的！有头节点尾节点！*没有头尾节点我要吐了

JAVA中没有指针的概念，只有引用数据类型，所以我们使用一个节点，充当指针得作用，毕竟new出来的都在堆里，你的节点名字也只是指向它而已

自己创造的链表节点部分：

1.注意让创造出来的指针域默认为Null比较方便操作

package linkedList;

public class Node {

public int age;

public String name;

public String nickName;

public Node nextNode = null;//默认是等于null的

public Node(int age, String name, String nickName, Node nextNode) {

this.age = age;

this.name = name;

this.nickName = nickName;

this.nextNode = nextNode;

}

public Node() {

}

@Override

public String toString() {

return "Node{" +

"age=" + age +

", name='" + name + '\'' +

", nickName='" + nickName + '\'' +

'}';

}

}

代码主题部分，增加了头节点和尾节点，方便操作：

1.尾插法，在尾指针后面插入数据

使用尾巴指针插入新的节点，并且让尾指针指向最后一个节点

public void add(int age,String name,String nickName) {//一个被发展的新下线

//追加节点

//使用尾指针进行追加节点，

headNode.age++;//使用头节点在存放链表长度

Node newNode = new Node();//先开辟一块空间，批一块地

//完成数值输入

newNode.age = age;

newNode.name = name;

newNode.nickName = nickName;

//想要新加入和上游生态连接上

tailPoint.nextNode = newNode;

tailPoint = newNode;//加入传销组织自己成为其中的一员

tailPoint.nextNode = null;//强调一下尾节点的next为null的问题

}

2.打印整个链表

一个临时指针从头开始

打印一个移动一次

直到打印到链表尾部

//遍历一下整个链表玩一玩

public void show(){

//先判断一下链表是不是空的

if(headNode.nextNode == null){

System.out.println("链表为空");

}

else{

Node temp = headPoint.nextNode;//从头节点的下一个节点

//利用一个临时节点从头开始遍历

while(temp != null){//相当于遍历到最后一个节点了

System.out.println(temp);//我已经改写toString方法了

temp = temp.nextNode;//指针后移

}

}

}

整个链表代码

真的难点在于链表删除的位置：

1.遍历到链表的要删除节点的前一个节点位置

2.完成上下连接

3.注意判断条件是temp.next.age == 条件，用前面一个节点，表示下一个节点

4.注意temp要从head开始，不然首节点判断不到

5.结束时候temp不要到最后一个节点才结束，因为尾巴指针已经被判断过了，

6.尾巴指针对应的节点很可能一开始就被删除了，注意

7.删除一个节点很容易，这个节点将下面交给上级就行了

package linkedList;

import com.sun.corba.se.impl.orb.ParserTable;

import java.sql.SQLOutput;

public class LinkedList {

private Node headNode = new Node();//建立一个头节点

//头节点代表整个链表的位置，比如某些时候用一个师长位置代表一个师

private Node headPoint = headNode;//头指针

private Node tailPoint = headPoint;//尾指针

//尾巴节点的next应该是为null的，我这里，所有新new的节点Node中next全部都是默认为null的

public LinkedList() {

this.headNode.age = 0;//给头节点中age设置初始值为0，用来存放链表长度

}

public int size(){

return this.headNode.age;//将头节点里age返回回去统计长度

}

public Node getHeadNode() {//将链表头节点返回回去

return headNode;

}

//这是尾插法

public void add(int age,String name,String nickName) {//一个被发展的新下线

//追加节点

//使用尾指针进行追加节点，

headNode.age++;//使用头节点在存放链表长度

Node newNode = new Node();//先开辟一块空间，批一块地

//完成数值输入

newNode.age = age;

newNode.name = name;

newNode.nickName = nickName;

//想要新加入和上游生态连接上

tailPoint.nextNode = newNode;

tailPoint = newNode;//加入传销组织自己成为其中的一员

tailPoint.nextNode = null;//强调一下尾节点的next为null的问题

}

//遍历一下整个链表玩一玩

public void show(){

//先判断一下链表是不是空的

if(headNode.nextNode == null){

System.out.println("链表为空");

}

else{

Node temp = headPoint.nextNode;//从头节点的下一个节点

//利用一个临时节点从头开始遍历

while(temp != null){//相当于遍历到最后一个节点了

System.out.println(temp);//我已经改写toString方法了

temp = temp.nextNode;//指针后移

}

}

}

//删除所有拥有同一数字的链表

public void deleteAll(int number){

//删除链表时候，要用到前一个节点去删除后一个节点，所以一定要从头节点开始遍历，不然没办法处理首节点

Node temp = headPoint;//创造出来一个遍历用的临时节点

boolean flag = false;//用来判断一下有没有找到节点

if(headNode.nextNode == null){//判空

System.out.println("链表为空");

}

else {

while (temp.nextNode != null){//无论如何都要将链表从头到尾都去看一下，将所有对上的节点都删除了

if(temp.nextNode.age == number){

this.headNode.age --;//先链表长度减一

flag = true;//找到了

temp.nextNode = temp.nextNode.nextNode;//上下线完成连接

}

temp = temp.nextNode;//链表移动

if(temp == null){//如果循环到达结尾跳出循环

break;

}

}

if(flag == false){

System.out.println("不存在这样的节点");

}

if(headNode.age == 0){

tailPoint = null;//元素被删完了，就让尾指针回去

}

}

}

//删除摸某一节点，以age去找到这个节点

public void delete(int number){

//由于每次需要使用的都是用前一个节点去判断下面那个节点符合不符合规定

//所以必须从头节点开始赋值，不然第一个节点不会被覆盖到

if(headNode.nextNode == null){

System.out.println("链表是空的");

}

else{

Node temp = headPoint;//一个指针从头开始找这个节点

boolean flag = false;//设置一个标志位，找到了的话，标志位为true

//删除节点，需要找被删除节点上一个节点，除掉下线，用上线，借助上线除掉下线

while (true){

//这里不要用尾指针进行判断，因为尾指针对应节点可能一开始就被删除

if(temp.nextNode == null){//当连链表遍历到尾指针的位置就退出

//前一个节点的后一个节点进行判断，所以尾指针上的节点已经被判断过了

break;//遍历完了就退出

}

if(temp.nextNode.age == number){//找到了

headNode.age = headNode.age - 1;//减去一个数量

flag = true;

//删除节点之后跳出循环

//先交代下线是谁

temp.nextNode = temp.nextNode.nextNode;//新的上下线连接成功

//旧的就被销毁了

break;//找到了就退出循环了

}

temp = temp.nextNode;//移动指针

}

//链表中不包含节点的处理

if(flag == true){

System.out.println("我们成功删除了链表");

}

else{

System.out.println("链表中不包含这个节点");

}

}

if(this.headNode.age == 0 ){

tailPoint = headPoint;//当链表被删除干净时候，将尾指针指向头节点等待下一次使用

}

}

//插入新的节点，根据年龄插入节点

public void insert(int pos,Node newNode){//插入位置，和插入的节点

Node temp = new Node();

temp = headPoint.nextNode;//开始遍历

boolean flag = false;

while(true){

if(temp.age == pos){

headNode.age = headNode.age + 1;//插入新节点了，链表长度增加

flag = true;//找到了

//完成插入

//插新的节点，上线介绍认识下线，然后和上线建立练习

newNode.nextNode = temp.nextNode;

//然后和上线建立联系

temp.nextNode = newNode;

break;//插入完成后就跳出

}

temp = temp.nextNode;//指针后移

if(temp == null){

break;//到最后了，跳出去

}

}

if(flag == false){

System.out.println("没有插入位置");

}

}

}

自己很喜欢的一段代码

//找到某个点，插入这个点前面

public boolean findOne(int no,String name){

//也许能找到这个点，找不到就报false，并且将这个点尾巴插入，用

//能找到的情况下，插入前头，找不到就尾巴插入

Node temp = headNode;

Node newNode = new Node(no,name);

boolean find = false;//默认是找不到

//找前面一个点

while(temp.next != null){

if(temp.next.no == no ){

find = !find;

break;//找到了就跳出去

}

temp = temp.next;//往后移动

}

//跳出来要么找到了，要么没找到

//找到了就插入

if(find){

newNode.next = temp.next;

temp.next = newNode;//连接上

}

//找不到就直接尾巴插入

if(!find){

addOne(no,name);

}

return find;//然后将find返回去，告诉计算机我们有没有找到

}

私信666领取资料