<div class="iteye-blog-content-contain" style="font-size: 14px"></div>
概念： 链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表通常由一连串节点组成，每个节点包含任意的实例数据和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）。链表数据的存取往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。
动手练习一下以增加对链表的理解：
练习：
1.定义一个链表类
2.链表中存储学生信息，根据学分从小到大的排序
代码如下：
package 链表;
public class Node {
public Object date;//数据域
public Node next;//引用域
public Node(Object date){
this.date=date;
}
}
package 链表;
/*
* 还应该再加一个方法：根据内容查找节点的位置，这样就可以通过修改指定位置的节点的方法达到修改指定内容的节点的目的
* 总结：
* 删除和插入时一定要特别注意头节点和尾节点，很容易出错
* */
public class LinkNode {
public Node root;//头节点
public Node rail;//尾节点
public int size=0;
/*
* 添加节点的方法*/
public void add(Node node){
if(size==0){
root=node;
rail=node;
size++;
return;
}
rail.next=node;
rail=node;
size++;
}
/*
* 找指定位置的节点*/
public Node get(int index){
if(index<0||index>=size){//index=0->size-1
return null;
}
Node node=root;
for(int i=0;i<index;i++){
//node.next=node;
node=node.next;
}
return node;
}
/*
* 修改指定位置的节点*/
public Object revamp(int index,Object date){
Node node=get(index);
get(index).date=date;
return node.date;
}
/*
* 在指定位置插入节点（插到指定位置的前面）*/
public void insert(int index,Node node){
size++;
node.next=get(index);//这两行代码的顺序不能弄反了
if(index==0){//如果要插入到第一个节点的前面，则要特殊处理
root=node;
}else {
get(index-1).next=node;
}
}
/*
* 删除指定位置的节点
* 返回被删除节点的数据
* */
public Object deletNode(int index){
Node node=null;
if(index<0||index>=size){
}
if(index==0){//如果删除的是头节点，则要特殊处理
if(size==1){//如果只有一个节点则直接删除即可
node=get(index);
root=null;
rail=null;
size--;
}
if(size>1){
node=get(index);
root=get(index).next;
size--;
}
}
if(index>0&&index<size-1){
node=get(index);//把要被删除的节点赋给中间变量
get(index-1).next=get(index).next;//删除节点的下一个节点赋给删除节点的上一个节点
size--;
}
if(index==size-1){//如果删除的是尾节点也要做特殊处理
if(size==1){//如果只有一个节点则直接删除即可
node=get(index);
root=null;
rail=null;
size--;
}
if(size>1){
node=get(index);
rail=get(index-1);
size--;
}
}
return node.date;
}
/*
* 删除节点(根据内容删除)
* 返回删除的节点位置
* */
public int deletNode(Object date){
int index=0;
for(int i=0;i<size;i++){
if(date.equals(get(i).date)){
index=i;
Node node=get(i);//把要被删除的节点赋给中间变量
if(i==0){//如果是要删除第一个节点的内容，则要特殊处理
root=get(i).next;
}
if(i==size-1){//如果是要删除最后一个节点的内容，则要特殊处理
rail=get(i-1);
}
if(i>0&&i<size-1){
get(i-1).next=get(i+1);//删除节点的下一个节点赋给删除节点的上一个节点
}
//node=null;
size--;
break;
}
}
return index;
}
/*
* 返回节点总数*/
public int size(){
return size;
}
}
package 链表;
public class Students {
private String name;
private String id;
private int score;
public Students(String name, String id, int score) {
this.name = name;
this.id = id;
this.score = score;
}
/*
* 重写equals()方法
* */
public boolean equals(Object st){
Students stu=(Students)st;
if(this.name.equals(stu.name)&&stu.score==this.score&&this.id.equals(stu.id)){
return true;
}
else return false;
}
public String toString() {
return "姓名：" + name + "\t学号：" + id + "\t学分：" + score;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
public int getScore() {
return score;
}
public void setScore(int score) {
this.score = score;
}
}
package 链表;
public class Test {
public static void main(String[] args) {
Test test=new Test();
java.util.Random random=new java.util.Random();
//创建链表对象
LinkNode link=new LinkNode();
//创建七个学生对象
Students st1=new Students("李 文","20140801",random.nextInt(100));
Students st2=new Students("李小东","20140802",random.nextInt(100));
Students st3=new Students("张晓江","20140803",random.nextInt(100));
Students st4=new Students("朱 丽","20140804",random.nextInt(100));
Students st5=new Students("肖 笑","20140805",random.nextInt(100));
Students st6=new Students("王 琳","20140806",random.nextInt(100));
Students st7=new Students("沈 文","20140807",random.nextInt(100));
//创建七个节点对象
Node node1=new Node(st1);
Node node2=new Node(st2);
Node node3=new Node(st3);
Node node4=new Node(st4);
Node node5=new Node(st5);
Node node6=new Node(st6);
Node node7=new Node(st7);
//把七个节点添加在链表里
link.add(node1);
link.add(node2);
link.add(node3);
link.add(node4);
link.add(node5);
link.add(node6);
link.add(node7);
/*
* 输出链表里的节点*/
System.out.println("排序前:");
test.output(link);//调用输出节点的方法
test.sort(link);//排序
System.out.println("按学分从低到高排序后:");
test.output(link);//调用输出节点的方法
System.out.println("------------------------------------------");
System.out.println();
/*
* 添加一个学生的信息
* */
System.out.println("--------- * 添加一个学生的信息*---------------------------------");
Students st8=new Students("王小晓","20140808",random.nextInt(100));
System.out.println("添加一个学生信息: "+st8.toString());
Node node8=new Node(st8);
link.add(node8);
//输出节点
System.out.println("添加了一个学生后:");
test.output(link);//调用输出节点的方法
test.sort(link);//排序
System.out.println("添加了一个学生后按学分从低到高排序后:");
test.output(link);//调用输出节点的方法
System.out.println("-------------------------------------------");
System.out.println();
/*
* 插入一个学生对象
* * */
System.out.println("----------* 插入一个学生对象* ---------------------------------");
Students st9=new Students("李重云","20140809",random.nextInt(100));
System.out.println("插入的学生信息: "+st9.toString());
Node node9=new Node(st9);
link.insert(0, node9);//在第三个位置插入
//输出节点
System.out.println("插入后:");
test.output(link);//调用输出节点的方法
test.sort(link);//排序
System.out.println("插入后按学分从低到高排序后:");
test.output(link);//调用输出节点的方法
System.out.println("-----------------------------------------");
System.out.println();
/*
* 删除指定位置的节点*/
System.out.println("------------* 删除指定位置的节点*-----------------------------");
Students st=(Students)link.deletNode(7);
System.out.println("指定删除第八个节点");
System.out.println("被删除的学生信息是： "+st.toString());
System.out.println("删除一个节点后:");
test.output(link);//调用输出节点的方法
System.out.println("-----------------------------------------");
System.out.println();
/*
* 根据内容删除指定位置的节点
* */
System.out.println("-----* 根据内容删除指定位置的节点 *--------------------------------------");
int index=link.deletNode(node9.date);
//输出节点
System.out.println("删除的学生是第"+(index+1)+"个\n该学生的信息是\t"+node9.date.toString());
System.out.println("删除第"+(index+1)+"一个学生后:");
test.output(link);//调用输出节点的方法
System.out.println("-----------------------------------------");
System.out.println();
/*
* 修改指定位置的节点
* */
System.out.println("------* 修改指定位置的节点*-----------------------------------");
Students stu=new Students("李文文","20140801",random.nextInt(100));
link.revamp(2, stu);
System.out.println("修改了第一个同学的信息，为："+stu.toString());
System.out.println("修改后:");
test.output(link);//调用输出节点的方法
test.sort(link);//排序
System.out.println("修改后按学分从低到高排序后:");
test.output(link);//调用输出节点的方法
System.out.println("-----------------------------------------");
System.out.println();
}
/*
* 输出链表里的节点方法*/
public void output(LinkNode link){
for(int i=0;i<link.size;i++){
System.out.println((i+1)+" "+link.get(i).date.toString());
}
}
//用冒泡排序法给学生的分数排序
public void sort(LinkNode link){
for(int j=0;j<link.size-1;j++){
for(int i=0;i<link.size-1;i++){
Students stu1 = (Students)link.get(i).date;
Students stu2 = (Students)link.get(i+1).date;
if(stu1.getScore() > stu2.getScore()){
Object temp=link.get(i).date;
link.get(i).date=link.get(i+1).date;
link.get(i+1).date=temp;
}
}
}
}
}
排序前: 1 姓名：李 文 学号：20140801 学分：43 2 姓名：李小东 学号：20140802 学分：97 3 姓名：张晓江 学号：20140803 学分：40 4 姓名：朱 丽 学号：20140804 学分：41 5 姓名：肖 笑 学号：20140805 学分：6 6 姓名：王 琳 学号：20140806 学分：51 7 姓名：沈 文 学号：20140807 学分：55 按学分从低到高排序后: 1 姓名：肖 笑 学号：20140805 学分：6 2 姓名：张晓江 学号：20140803 学分：40 3 姓名：朱 丽 学号：20140804 学分：41 4 姓名：李 文 学号：20140801 学分：43 5 姓名：王 琳 学号：20140806 学分：51 6 姓名：沈 文 学号：20140807 学分：55 7 姓名：李小东 学号：20140802 学分：97 ------------------------------------------ --------- * 添加一个学生的信息*--------------------------------- 添加一个学生信息: 姓名：王小晓 学号：20140808 学分：25 添加了一个学生后: 1 姓名：肖 笑 学号：20140805 学分：6 2 姓名：张晓江 学号：20140803 学分：40 3 姓名：朱 丽 学号：20140804 学分：41 4 姓名：李 文 学号：20140801 学分：43 5 姓名：王 琳 学号：20140806 学分：51 6 姓名：沈 文 学号：20140807 学分：55 7 姓名：李小东 学号：20140802 学分：97 8 姓名：王小晓 学号：20140808 学分：25 添加了一个学生后按学分从低到高排序后: 1 姓名：肖 笑 学号：20140805 学分：6 2 姓名：王小晓 学号：20140808 学分：25 3 姓名：张晓江 学号：20140803 学分：40 4 姓名：朱 丽 学号：20140804 学分：41 5 姓名：李 文 学号：20140801 学分：43 6 姓名：王 琳 学号：20140806 学分：51 7 姓名：沈 文 学号：20140807 学分：55 8 姓名：李小东 学号：20140802 学分：97 ------------------------------------------- ----------* 插入一个学生对象* --------------------------------- 插入的学生信息: 姓名：李重云 学号：20140809 学分：10 插入后: 1 姓名：李重云 学号：20140809 学分：10 2 姓名：肖 笑 学号：20140805 学分：6 3 姓名：王小晓 学号：20140808 学分：25 4 姓名：张晓江 学号：20140803 学分：40 5 姓名：朱 丽 学号：20140804 学分：41 6 姓名：李 文 学号：20140801 学分：43 7 姓名：王 琳 学号：20140806 学分：51 8 姓名：沈 文 学号：20140807 学分：55 9 姓名：李小东 学号：20140802 学分：97 插入后按学分从低到高排序后: 1 姓名：肖 笑 学号：20140805 学分：6 2 姓名：李重云 学号：20140809 学分：10 3 姓名：王小晓 学号：20140808 学分：25 4 姓名：张晓江 学号：20140803 学分：40 5 姓名：朱 丽 学号：20140804 学分：41 6 姓名：李 文 学号：20140801 学分：43 7 姓名：王 琳 学号：20140806 学分：51 8 姓名：沈 文 学号：20140807 学分：55 9 姓名：李小东 学号：20140802 学分：97 ----------------------------------------- ------------* 删除指定位置的节点*----------------------------- 指定删除第八个节点 被删除的学生信息是： 姓名：李小东 学号：20140802 学分：97 删除一个节点后: 1 姓名：肖 笑 学号：20140805 学分：6 2 姓名：李重云 学号：20140809 学分：10 3 姓名：王小晓 学号：20140808 学分：25 4 姓名：张晓江 学号：20140803 学分：40 5 姓名：朱 丽 学号：20140804 学分：41 6 姓名：李 文 学号：20140801 学分：43 7 姓名：王 琳 学号：20140806 学分：51 ----------------------------------------- -----* 根据内容删除指定位置的节点 *-------------------------------------- 删除的学生是第1个 该学生的信息是 姓名：肖 笑 学号：20140805 学分：6 删除第1一个学生后: 1 姓名：李重云 学号：20140809 学分：10 2 姓名：王小晓 学号：20140808 学分：25 3 姓名：张晓江 学号：20140803 学分：40 4 姓名：朱 丽 学号：20140804 学分：41 5 姓名：李 文 学号：20140801 学分：43 6 姓名：王 琳 学号：20140806 学分：51 ----------------------------------------- ------* 修改指定位置的节点*----------------------------------- 修改了第一个同学的信息，为：姓名：李文文 学号：20140801 学分：66 修改后: 1 姓名：李重云 学号：20140809 学分：10 2 姓名：王小晓 学号：20140808 学分：25 3 姓名：李文文 学号：20140801 学分：66 4 姓名：朱 丽 学号：20140804 学分：41 5 姓名：李 文 学号：20140801 学分：43 6 姓名：王 琳 学号：20140806 学分：51 修改后按学分从低到高排序后: 1 姓名：李重云 学号：20140809 学分：10 2 姓名：王小晓 学号：20140808 学分：25 3 姓名：朱 丽 学号：20140804 学分：41 4 姓名：李 文 学号：20140801 学分：43 5 姓名：王 琳 学号：20140806 学分：51 6 姓名：李文文 学号：20140801 学分：66 -----------------------------------------
总结：写插入方法、删除方法、添加方法时一定要对链表的头节点和尾节点进行特殊的处理，不然在用链表的头尾部分对节点进行处理时很容易报空指针异常的错误。
相关推荐
N名学生的成绩已在主函数中放入一个带头节点的链表结构中，h指向链表的头节点。
数据结构 初始化链表，插入删除节点，遍历链表,链表长度，找出中间节点
同样，需要遍历链表找到目标节点，然后改变前一个节点的指针域，使其指向目标节点的后继节点，从而断开目标节点与链表的连接。 4. 更新：修改链表中某个城市的坐标或名字。这需要先找到目标节点，然后直接更新其...
双向链表与单链表的主要区别在于每个节点除了包含数据外，还包含两个指针，一个指向其前一个节点（prev），另一个指向其后一个节点（next）。这种设计使得在链表中进行插入和删除操作更加灵活，因为我们可以轻松地...
- **释放内存**：最后，由于我们已经切断了目标节点与链表的联系，可以安全地释放目标节点所占用的内存。 ### 2. 链表删除的特殊情况 #### 2.1 删除头节点 删除头节点是链表操作中的特例，因为头节点没有前一个...
链表节点移除（删除）在FreeRTOS中的实现 在FreeRTOS中，链表节点移除（删除）的实现是通过uxListRemove函数来实现的，该函数将节点从链表中移除，并更新链表的索引指针和节点计数器。 uxListRemove函数的实现中，...
2. **删除记录**：删除操作涉及到查找指定的联系人节点，然后修改前一个节点的指针，使其指向被删除节点的下一个节点，从而断开被删除节点与链表的连接。如果节点是链表的头节点，需要特殊处理，通常将第二个节点设...
2. **删除学生**：根据特定条件（如学号或姓名）查找目标节点，然后修改其前一个节点的指针，使其指向目标节点的下一个节点，从而断开目标节点与链表的联系。 3. **修改学生信息**：同样根据条件查找目标节点，更新...
操作一个链表，链表中的节点有两个指针，一个指向下一个节点， 一个指向下下一个节点，如果下一个节点或者下下一个节点为空，则为null。 操作为插入，删除，修改。 博客：...
带头节点的链表 并对其排序 有插入节点和遍历节点
这是一个单向链表，它具有插入与删除节点的功能。Entry类实现了链表的各节点。
3. 完成遍历后，新链表的next指针应该已经正确连接，现在可以断开与原链表的联系，形成独立的副本。 总的来说，理解和解决这个问题需要对链表、指针操作以及数据结构复制有深入的理解。在Java这样的面向对象语言中...
循环链表与普通链表的主要区别在于，它的最后一个节点指针并不指向空值（NULL），而是指向链表的第一个元素，形成一个环状结构。这样做的好处是，无论当前指针处于链表的哪个位置，我们都可以通过一次遍历访问到链表...
为了实现按大小排列，我们需要在添加节点时比较新节点与链表中现有节点的大小，确保新节点始终被插入到正确的位置。这可以使用双向链表来简化，因为它允许我们在链表的任何位置快速插入和删除节点。 对于双向链表，...
4. **信息删除**：删除操作涉及找到要删除的学生节点，然后修改其前一个节点的指针，使其指向被删除节点的后继节点，从而断开被删除节点与链表的连接。 5. **排序显示**：为了方便查看，系统可能还提供了按某种标准...
删除用户时，需要找到待删除节点，然后更改其前一个节点的指针域，使其指向待删除节点的后继节点，从而断开待删除节点与链表的联系。查询用户信息通常通过遍历链表来实现，根据给定的关键信息（如学号或工号）找到...
数据结构经典算法演示，这里是链表-插入节点的代码演示
链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的引用。在本场景中，我们讨论的是一个名为“链表节点类”的实现，它专门用于管理链表中的节点指针，并提供了两种不同的节点提取...
与数组的连续存储方式不同，链表的每个元素都存储在一个独立的节点中，这些节点通过指针相互连接，形成一个链式结构。这样的结构不依赖于物理存储位置的连续性，提供了动态内存管理的便利，非常适合在不知道数据大小...
这个函数需要遍历链表，检查当前节点与后续节点的数据是否相同。如果相同，则将当前节点指向下一个节点的下一个节点，跳过重复的节点。为了实现这个功能，我们可以创建一个辅助函数`deleteDupNodes()`： ```c ...