链表的概念及功能实现

一、链表之单向链表

前面我们使用顺序储存结构实现的顺序表，虽然查询的时候很快，但在进行元素的增加或者删除的时候:比较麻烦，需要你去移动大量的元素把数据删除或者增加。

链表里的数据是以结点方式来表示的，每一个结点的组成是由：数据+指针来组成的。

一个结点的结构是这样的：

单向链表：

单链表是一种链式储存结构，在物理储存单元不连续，非顺序。
由多个结点组成的，每一个结点都是有一个数据域+指针域组成，数据域是用来存储数据元素的，指针用来指向后面的节点。
链表分成带头结点的链表跟不带头结点的链表。
单链表的头节点里不储存数据，它的指针指向真正存储有数据的第一个链表节点。

带头结点的单链表：

该链表储存地址：

单链表的具体实现，首先需要定义一个类表示每个结点的信息（假设每个结点都是课程的信息）：

class CourseNode{public int id;public String courseName;public CourseNode next;public CourseNode(int id, String courseName) {this.id = id;this.courseName = courseName;}@Overridepublic String toString() {return "CourseNode{" +"id=" + id +", courseName='" + courseName + '\'' +", next=" + next +'}';}
}

然后定义单链表类：

class CourseLinke{//初始化头节点public CourseNode head = new CourseNode(0,"");//链表有效元素个数private int length=0;
}

添加课程的方法：

public void addCourse(CourseNode node){//辅助的指针CourseNode cur = head;//遍历链表，找到最后一个节点while (true){if(cur.next==null){break;}cur=cur.next;}cur.next=node;length++;}

遍历课程的方法：

public void showCourse(){//定义辅助的指针CourseNode cur = head;if(cur.next==null){System.out.println("链表为空，不能输出");return;}while (true){if(cur.next==null){System.out.println("课程输出完成");return;}System.out.println(cur.next);cur=cur.next;}}

删除课程的方法：

public void delCourse(int id){//定义辅助的指针CourseNode cur = head;if(cur.next == null){return;}//记录是否找到课程boolean flag = false;while (cur.next!=null){if(cur.next.id==id){flag=true;break;}//一直遍历cur=cur.next;}if(flag){//删除节点cur.next=cur.next.next;length--;}else {System.out.printf("要删除的节点%d没有找到",id);}}

修改课程的方法：

public void update(CourseNode node){CourseNode cur = head;boolean flag = false;while (cur.next!=null){if(cur.next.id==node.id){flag=true;break;}cur = cur.next;}if(flag){cur.next.id=node.id;cur.next.courseName=node.courseName;}else {System.out.println("没有找到要修改的课程");}}

接下来我们要实现查找倒数第K个课程，首先我们要先得到链表的长度：

public int getLength(){return length;}

查找倒数第K个课程:

//1、求解链表的长度   2、遍历到链表长度-K+1public CourseNode getLastCourse(int k){CourseNode cur = head;if(cur.next==null){System.out.println("链表为空");return null;}int length = getLength();if(k==0||k>length){throw new IllegalArgumentException("参数不合法");}for (int i=0;i<length-k+1;i++){cur=cur.next;}return cur;}