1)链表是以节点的方式来存储,是链式存储
2)每个节点包含 data 域， next 域：指向下一个节点.
3)如图：发现链表的各个节点不一定是连续存储.
4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
创建单链表的思路：
1. 先创建一个head 头节点， 作用就是表示单链表的头
2. 后面我们每添加一个节点，就直接加入到链表的最后
按照编号顺序添加节点的思路：
1. 首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定
2. 新的节点.next = temp.next
3. 将temp.next = 新的节点
从单链表中删除一个节点的思路
1. 先找到需要删除的这个节点的前一个节点 temp
2. temp.next = temp.next.next
3. 被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收
遍历思路：
1. 通过一个辅助变量遍历，帮助遍历整个链表
示例：使用带head头的单向链表实现 –英雄排行榜管理
1) 完成对英雄人物的 增删改查 操作， 注 : 删除和修改 , 查找 2) 第一种方法在添加英雄时，直接添加到链表的尾部 3) 第二种方式在添加英雄时 ，根据排名将英雄插入到指定位置 ( 如果有这个排名，则添加失败，并给出提示 ) 一、HeroNode类的定义：class HeroNode{
public int No;
public String nickname;
public String name;
public HeroNode next;
public HeroNode(int no, String nickname, String name) {
No = no;
this.nickname = nickname;
this.name = name;
}
@Override
public String toString() {
return "HeroNode{" +
"No=" + No +
", nickname='" + nickname + ''' +
", name='" + name + ''' +
", ";
}
}
二、SingleLinkedList 类的定义：
class SingleLinkedList{
//初始化头加点，不存放具体数据
public final HeroNode head=new HeroNode(0,"","");
... ...
1.添加节点 add，插在末尾
public void add(HeroNode heroNode){
//需要辅助变量temp来遍历链表
HeroNode temp=head;
while (true){
if(temp.next==null){
temp.next=heroNode;
heroNode.next=null;
break;
}
temp=temp.next;
}
}
测试结果：
@Test
public void testAdd(){
SingleLinkedList linkedList=new SingleLinkedList();
linkedList.add(new HeroNode(1,"wz","wangzhuang"));
linkedList.add(new HeroNode(2,"zp","zhouping"));
linkedList.add(new HeroNode(3,"lf","lufei"));
linkedList.showList();
}
HeroNode{No=1, nickname='wz', name='wangzhuang',
HeroNode{No=2, nickname='zp', name='zhouping',
HeroNode{No=3, nickname='lf', name='lufei',
2.添加结点 addByOrder，按照NO序号按顺序插入
public void addByOrder(HeroNode heroNode){
HeroNode temp= head;//用辅助节点遍历到待插入的位置
boolean flag=false;// 1-编号已存在，取消本次操作 0-编号不存在，可以插
while (true){
if(temp.next==null) break;//已经指向链表最后
if(temp.next.No>heroNode.No) break;//找对了位置，在temp和temp.next间插入
if(temp.next.No==heroNode.No){
flag=true;
break;
}//编号已存在，取消操作
temp=temp.next;
}
if(flag){
System.out.println("编号 "+heroNode.No+" 已存在，不能重复插入!");
}else{
heroNode.next=temp.next; //新节点的next指向它后面的节点
temp.next=heroNode;//新节点前的结点的next指向新节点
}
}
测试结果：
@Test
public void testAddByOrder(){
SingleLinkedList linkedList=new SingleLinkedList();
linkedList.addByOrder(new HeroNode(1,"wz","wangzhuang"));
linkedList.addByOrder(new HeroNode(3,"zp","zhouping"));
linkedList.addByOrder(new HeroNode(2,"lf","lufei"));
linkedList.addByOrder(new HeroNode(4,"pp","pipi"));
linkedList.addByOrder(new HeroNode(1,"ff","test"));
linkedList.addByOrder(new HeroNode(2,"ff","test"));
linkedList.showList();
}
编号 1 已存在，不能重复插入!
编号 2 已存在，不能重复插入!
HeroNode{No=1, nickname='wz', name='wangzhuang',
HeroNode{No=2, nickname='lf', name='lufei',
HeroNode{No=3, nickname='zp', name='zhouping',
HeroNode{No=4, nickname='pp', name='pipi',
3.修改节点 update，根据NO.
public void update(HeroNode node){
HeroNode temp=head.next;
boolean flag=false;
//通过辅助变量temp遍历到待修改节点
while(true){
if(temp==null)break;
if(temp.No == node.No){
flag=true;
break;
}
temp=temp.next;
}
if(flag) {
temp.name = node.name;
temp.nickname = node.nickname;
}else System.out.println("编号 "+node.No+" 的结点未找到，修改失败!");
}
测试结果：
@Test
public void testUpdate(){
SingleLinkedList linkedList=new SingleLinkedList();
linkedList.addByOrder(new HeroNode(1,"wz","wangzhuang"));
linkedList.addByOrder(new HeroNode(3,"zp","zhouping"));
linkedList.addByOrder(new HeroNode(2,"lf","lufei"));
linkedList.addByOrder(new HeroNode(4,"pp","pipi"));
linkedList.update(new HeroNode(1,"wzz","wangzhuangzhuang"));
linkedList.update(new HeroNode(666,"wzz","wangzhuangzhuang"));
linkedList.showList();
}
编号 666 的结点未找到，修改失败!
HeroNode{No=1, nickname='wzz', name='wangzhuangzhuang',
HeroNode{No=2, nickname='lf', name='lufei',
HeroNode{No=3, nickname='zp', name='zhouping',
HeroNode{No=4, nickname='pp', name='pipi',
4.删除节点 delete，根据NO.
public void delete(int no){
HeroNode temp=head;
boolean flag=false;
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+" 的结点未找到，删除失败!");
}
测试结果：
@Test
public void testDelete(){
SingleLinkedList linkedList=new SingleLinkedList();
linkedList.addByOrder(new HeroNode(1,"wz","wangzhuang"));
linkedList.addByOrder(new HeroNode(3,"zp","zhouping"));
linkedList.addByOrder(new HeroNode(2,"lf","lufei"));
linkedList.addByOrder(new HeroNode(4,"pp","pipi"));
System.out.println(linkedList.getLength());
linkedList.delete(1);
linkedList.delete(666);
linkedList.showList();
System.out.println(linkedList.getLength());
}
4
编号 666 的结点未找到，删除失败!
HeroNode{No=2, nickname='lf', name='lufei',
HeroNode{No=3, nickname='zp', name='zhouping',
HeroNode{No=4, nickname='pp', name='pipi',
3
5.判断链表是否为空 isEmpty
public boolean isEmpty(){
return (head.next==null);
}
6.遍历链表 showList
public void showList(){
if(isEmpty()){
System.out.println("链表为空！");
return;
}
HeroNode temp=head.next;
while(true){
System.out.println(temp);
if(temp.next==null) break;
temp=temp.next;
}
}
7.统计节点个数getLength
public int getLength(){
HeroNode temp=head;
int length=0;
while(temp.next != null){
temp=temp.next;
length++;
}
return length;
}
三、几个面试题
1.查找单链表中倒数第index个节点
public HeroNode getNodeByReverseOrder(int index){
HeroNode temp=head;
int size=getLength();
if(index<=0 || index>size){
System.out.println("索引输入有误！");
return null;
}
for(int i=0;i<=(size-index);i++){
temp=temp.next;
}
return temp;
}
测试：
@Test
public void testGetNodeByReverseOrder(){
SingleLinkedList linkedList=new SingleLinkedList();
linkedList.addByOrder(new HeroNode(1,"wz","wangzhuang"));
linkedList.addByOrder(new HeroNode(3,"zp","zhouping"));
linkedList.addByOrder(new HeroNode(2,"lf","lufei"));
linkedList.addByOrder(new HeroNode(4,"pp","pipi"));
System.out.println(linkedList.getNodeByReverseOrder(2)); //取倒数第二个
}
HeroNode{No=3, nickname='zp', name='zhouping',
2.将链表反转
public void reverseLinkedList(){
//空链表或只有一个节点，退出
if(head.next==null || head.next.next==null) return;
//定义一个翻转头节点
HeroNode reverseHead=new HeroNode(0,"","");
//next暂存当前节点cur的下一个节点
HeroNode nextNode=null;
//定义一个用于遍历的cur，每遍历一个节点就把该节点取出加到reverseHead后面。
HeroNode cur=head.next;
//每遍历一个节点就把该节点取出加到reverseHead后面
while(cur != null){
nextNode=cur.next;//暂存当前节点的下一个节点
cur.next=reverseHead.next;//新节点的next指向新链表的最前端（头插）
reverseHead.next=cur;//reverseHead的next指向新节点
cur=nextNode;//让cur指向它在旧链表中的下一节点,继续遍历
}
head.next=reverseHead.next;
}
测试：
@Test
public void testReverselinkedList(){
SingleLinkedList linkedList=new SingleLinkedList();
linkedList.addByOrder(new HeroNode(1,"wz","wangzhuang"));
linkedList.addByOrder(new HeroNode(3,"zp","zhouping"));
linkedList.addByOrder(new HeroNode(2,"lf","lufei"));
linkedList.addByOrder(new HeroNode(4,"pp","pipi"));
linkedList.showList();
System.out.println();
linkedList.reverseLinkedList();
linkedList.showList();
}
HeroNode{No=1, nickname='wz', name='wangzhuang',
HeroNode{No=2, nickname='lf', name='lufei',
HeroNode{No=3, nickname='zp', name='zhouping',
HeroNode{No=4, nickname='pp', name='pipi',
HeroNode{No=4, nickname='pp', name='pipi',
HeroNode{No=3, nickname='zp', name='zhouping',
HeroNode{No=2, nickname='lf', name='lufei',
HeroNode{No=1, nickname='wz', name='wangzhuang',
3.倒序打印单链表
public void reversePrint(){
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());
}
