1)链表是以节点的方式来存储,是链式存储
2)每个节点包含data域和next域,data域用来存放数据,next域指向下一个节点
3)链表的各个节点不一定是连续存储的
4)链表分带头节点的链表和没有头节点的链表,根据实际需求确定
2.单向链表
单向链表的节点包括两个元素,分别为数据和指针
(1)定义节点
package datastructure.LinkedList.SingalLinkedList;
public class HeroNode {
public int no;
public String name;
public String nickName;
HeroNode next;
public HeroNode(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
}
//重写toString方法
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + ''' +
", nickName='" + nickName + ''' +
'}';
}
}
(2)单向链表的实现(增删改查)
package datastructure.LinkedList.SingalLinkedList;
import java.util.Stack;
public class SingalLinkedList {
//初始化头节点
private HeroNode head = new HeroNode(0,"","");
//添加节点到单向链表
//不需要考虑节点的编号,找到最后一个节点将新节点加入到后面
//将最后一个节点的next指向新加入的节点
public void add(HeroNode heroNode){
//头节点不能动,从头节点开始遍历
//设定一个临时变量temp
HeroNode temp = head;
while (true){
//找到了链表的末尾
if (temp.next == null) {
break;
}
//未找到,则后移
temp = temp.next;
}
temp.next = heroNode;
}
//根据排名添加节点
public void addByOrder(HeroNode heroNode){
//头节点不能动,设置临时节点temp
//设置一个标签flag,默认为false
HeroNode temp = head;
boolean flag = false;//flag标签表示添加的编号是否已经存在
//链表末尾
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.no > heroNode.no) {//位置已经找到
break;
} else if (temp.next.no == heroNode.no) {
System.out.println("编号重复!");
return;
}
temp = temp.next;
}
heroNode.next = temp.next;
temp.next = heroNode;
}
//修改节点
//根据no值来修改,即no不能修改
public void update(HeroNode newHeroNode){
if (head.next == null){
System.out.println("链表为空!");
return;
}
HeroNode temp = head.next;
boolean flag = false;//判断标识符false表示未找到,true表示已经找到
//遍历
while (true){
if (temp == null) {
break;
}else if(temp.no == newHeroNode.no){
flag = true;
break;
}
temp = temp.next;//后移
}
if (flag){
//找到了
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
}else{
//未找到
System.out.println("没有找到编号为"+newHeroNode.no+"的英雄!");
}
}
//删除节点
public void del(int no){
//判断是否为空链表
if (head.next == null){
System.out.println("链表为空!");
return ;
}
HeroNode temp = head;
boolean flag = false;//标识符,false表示未找到。true表示已经找到
while (true){
if (temp.next == null) {
break;
}
if (temp.next.no == no){
flag = true;
break;
}
temp = temp.next;//未找到则后移
}
if (flag){
temp.next = temp.next.next;
}else {
System.out.println("未找到编号为"+no+"的英雄,无法进行删除");
}
}
//遍历节点
public void list(){
//判断链表是否为空
if (head.next == null) {
System.out.println("原链表为空!");
return;
}
//头节点不能移动,设置辅助节点temp
HeroNode temp = head.next;
while (true){
//判断是否到了链表末尾
if (temp == null) {
break;
}
//输出节点信息
System.out.println(temp);
//节点后移
temp = temp.next;
}
}
//求单链表的节点个数
public int getLength(HeroNode head){
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空!");
return 0;
}
HeroNode temp = head.next;
int sum = 0;
while (true){
if (temp == null) {
break;
}
sum++;
temp = temp.next;//后移
}
return sum;
}
public HeroNode getHead() {
return head;
}
//查找单链表的倒数第K个节点
//获取链表的总长度 size=getLength()
//遍历到size-k即可
public HeroNode findLastIndexNode(HeroNode head,int index){
//判断链表是否为空
if (head.next == null) {
return null;
}
int size = getLength(getHead());
HeroNode temp = head.next;
if (index < 0 || index > size){
return null;
}
//
for (int i = 0;i < size-index;i++){
temp = temp.next;
}
return temp;
}
//单链表反转
public void reverseList(HeroNode head){
//若链表为空或者只有一个节点,则无需反转
if (head.next == null || head.next.next == null){
return;
}
HeroNode temp = head.next;
HeroNode next = null;
HeroNode reverseHead = new HeroNode(0,"","");
//遍历原来的链表,每遍历一个将该节点取出,并放入新链表reverseHead的最前面
while (temp != null){
next = temp.next;//保存当前节点的下一个节点
temp.next = reverseHead.next;//将当前节点点的下一个节点指向新链表最前端
reverseHead.next = temp;//将新遍历出来的节点插入到新链表的最前端
temp = next;//后移
}
head.next = reverseHead.next;//将反转的链表放回到原始的链表
}
//从尾到头打印单链表
public void reversePrint(HeroNode head){
//判断链表是否为空
if (head.next == null){
return;
}
Stack stack = new Stack();
HeroNode temp = head.next;
//将链表的节点压入栈中
while (temp != null){
stack.push(temp);
temp = temp.next;
}
//弹栈打印
while (stack.size()>0){
System.out.println(stack.pop());
}
}
}
3.关于单向链表的几道面试题
(1)求单链表中有效节点的个数
思路分析:如果链表带有头节点,不需要统计头节点
先判断链表是否为空,为空则返回0
定义一个辅助变量,该辅助变量指向头节点的下一个节点,再进行遍历即可
//求单链表的节点个数
publicintgetLength(HeroNode head){
//判断链表是否为空
if(head.next==null){
System.out.println("链表为空!");
Return 0;
}
HeroNodetemp=head.next;
Int sum=0;
while(true){
if(temp==null){
break;
}
sum++;
temp=temp.next;//后移
}
Return sum;
}
(2)查找单链表中的倒数第 k 个结点 【新浪面试题】
思路:1.编写一个方法,接收head节点,同时接收一个index,index表示倒数第index个节点
2.把链表从头到尾遍历,得到链表的总长度size
3.判断index的大小,当index<0 或者 index > size 则返回null
4.从链表的第一个开始遍历(size-index)个,从而得到该节点
//查找单链表的倒数第K个节点
//获取链表的总长度size=getLength()
//遍历到size-k即可
Public HeroNode findLastIndexNode(HeroNode head,int index){
//判断链表是否为空
if(head.next==null){
Return null;
}
Int size=getLength(getHead());
HeroNode temp=head.next;
if(index<0||index>size){
Return null;
}
//
for(inti=0;i
3.单向链表的反转【腾讯面试题】
//单链表反转
Public void reverseList(HeroNode head){
//若链表为空或者只有一个节点,则无需反转
if(head.next==null||head.next.next==null){
return;
}
HeroNode temp=head.next;
HeroNode next=null;
HeroNode reverseHead=new HeroNode(0,"","");
//遍历原来的链表,每遍历一个将该节点取出,并放入新链表reverseHead的最前面
while(temp!=null){
next=temp.next;//保存当前节点的下一个节点
temp.next=reverseHead.next;//将当前节点点的下一个节点指向新链表最前端
reverseHead.next=temp;//将新遍历出来的节点插入到新链表的最前端
temp=next;//后移
}
head.next=reverseHead.next;//将反转的链表放回到原始的链表
}
4.从尾到头打印单向链表
//从尾到头打印单链表
Public void reverse Print(HeroNodehead){
//判断链表是否为空
if(head.next==null){
return;
}
Stackstack=new Stack();
HeroNode temp=head.next;
//将链表的节点压入栈中
while(temp!=null){
stack.push(temp);
temp=temp.next;
}
//弹栈打印
while(stack.size()>0){
System.out.println(stack.pop());
}
}
4.双向链表
- 单向链表的缺点分析:
1) 单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找。
2) 单向链表不能自我删除,需要靠辅助节点 ,而双向链表,则可以自我删除,所以前面我们单链表删除时节点,总是找到 temp,temp 是待删除节点的前一个节点
- 双向链表增删改查思路分析
(1)遍历
方式与单链表一样,不过可以向前也可以向后
(2)添加(默认添加到双向链表最后)
1.找到双向链表的最厚一个节点·
2.temp.next = newHeroNode
3.newHeroNode.pre = temp;
(3) 修改
思路与单向链表一样
(4)删除
(1) 因为是双向链表,因此,我们可以实现自我删除某个节点
(2) 直接找到要删除的这个节点,比如 temp
(3) temp.pre.next = temp.next
(4) temp.next.pre = temp.pre;
双向链表节点:
package datastructure.LinkedList.DoubleLinkedList;
public class HeroNode1 {
public int no;
public String name;
public String nickName;
HeroNode1 next;//指向下一个节点
HeroNode1 pre;//指向上一个节点
public HeroNode1(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
}
@Override
public String toString() {
return "HeroNode1{" +
"no=" + no +
", name='" + name + ''' +
", nickName='" + nickName + ''' +
'}';
}
}
双向链表
package datastructure.LinkedList.DoubleLinkedList;
public class DoubleLinkedList {
//初始化头节点
private HeroNode1 head = new HeroNode1(0,"","");
//添加节点到双向链表
public void add(HeroNode1 heroNode){
HeroNode1 temp = head;
while (true){
//找链表的末尾
if (temp.next == null) {
break;
}
temp = temp.next;//后移
}
//形成一个双向链表节点
temp.next = heroNode;
heroNode.pre = temp;
}
//遍历
public void list(){
//判断链表是否为空
if (head.next == null){
System.out.println("链表为空");
return;
}
//设置辅助节点temp
HeroNode1 temp = head.next;
while (temp != null){
System.out.println(temp);
temp = temp.next;
}
}
//修改节点
public void update(HeroNode1 newHeroNode){
//判断链表是否为空
if (head.next == null){
System.out.println("链表为空!");
return;
}
HeroNode1 temp = head.next;
boolean flag = false;//标签,默认为false没有找到,true表示找到该节点
while (true){
if (temp.next == null) {
break;
}
if (temp.no == newHeroNode.no){
flag = true;
break;
}
temp = temp.next;
}
if (flag){
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
}else{
System.out.println("没有找到编号为"+newHeroNode.no+"的节点");
}
}
public HeroNode1 getHead() {
return head;
}
//删除节点
public void del(int index){
//判断链表是否为空
if(head.next == null){
System.out.println("链表为空!");
return;
}
//设置辅助节点temp
HeroNode1 temp = head.next;
boolean flag = false;//标识符false表示没有找到该节点,true表示找到了该节点
while (true){
if (temp == null){
break;
}
if (temp.no == index){
flag = true;
break;
}
temp = temp.next;
}
if (flag){
if (temp.next == null) {
//最后一个节点
temp.pre.next = temp.next;
}else {
temp.pre.next = temp.next;//删除节点temp
temp.next.pre = temp.pre;//若为最后一个节点,则不需要执行这个
}
}else{
System.out.printf("链表中没有编号为%d的英雄",index);
}
}
//按照编号顺序添加
public void addByOrder(HeroNode1 heroNode1){
HeroNode1 temp = head;
boolean flag = false;//标识符,判断是否具有重复
while (true){
if (temp.next == null){
break;
}
if (temp.next.no > heroNode1.no){
break;
}else if(temp.next.no == heroNode1.no){
flag = true;
break;
}
temp = temp.next;
}
if (flag ){
System.out.println("加入的节点"+heroNode1.no+"编号重复");
}else{
heroNode1.next = temp.next;
if (temp.next != null){
temp.next.pre = heroNode1;
}
temp.next = heroNode1;
heroNode1.pre = temp;
}
}
}



