目录

链表的定义链表的结构单向不带头非循环链表(重点掌握，面试常考)单向带头非循环链表单向带头循环链表 自己实现一个链表(一定自己动手实现五遍以上）单向不带头非循环链表(重点)接口(方法)代码示例 顺序表和链表的区别

链表的定义

​​​

链表就像每个节点串起来一样构成了一串，每个节点都是一个节点对象

其中我们对于每个节点会去划分域，分为data域跟next域两种.

data代表数值域，next代表引用，用于存取下一个节点的地址.

链表的结构

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

单向、双向

带头、不带头

循环、非循环

单向组合起来一共有以下几种：

单向、带头、循环、

单向、不带头、非循环(面试中经常考到的,也是我们重点掌握内容)

单向、带头、非循环

单向、不带头、循环

单向不带头非循环链表(重点掌握，面试常考)

在单向不带头非循环链表中，第一个节点我们称之为头节点，最后一个节点我们称之为尾节点

同时单向链表的尾节点的next域为null,因为尾结点不再指向任何一个结点

同时我们可以发现链表上的地址不同于顺序表的是，链表的地址并不是连续的，链表中节点的相连是通过next域来实现的

单向带头非循环链表

在单向有头非循环链表中，我们是用一个专门的节点来作为头节点的，这个节点没有data这个数值域，只有next指针域，这个指针域用来存储我们第一个数据节点的地址，且这个头节点是无法删除的，它就像一个哨兵，指向我们第一个数据节点。

单向带头循环链表

自己实现一个链表(一定自己动手实现五遍以上）

单向不带头非循环链表(重点)

接口(方法)

//头插法（优化和非优化方法)

public void addFirst(int data);

//尾插法（优化和非优化方法)

public void addLast(int data);

//任意位置插入,第一个数据节点为0号下标

public boolean addIndex(int index,int data);

//查找关键字key是否在单链表当中

public boolean contains(int key);

//删除第一次出现关键字为key的节点

public void remove(int key);

//得到单链表的长度

public int size();

//遍历输出链表

public void display();

//清空单链表

public void clear();

//找到链表的最后一个节点

public void findLastNode();

//找到链表的倒数第二个节点

public void findLastTwoNode();

//找到链表的第n个节点

public Node findNumber(int n);

代码示例

/*** @author SongBiao* @Date /1/18* 自己实现一个单向无头非循环链表*///Node类适用于创建每个单个的节点对象class Node {//代表我们的数值域public int data;//next是用来存取下一个节点对象的地址的，所以是Node类型，说明其也是一个引用public Node next;public Node() {}public Node(int data) {this.data = data;}}public class MyLinkedList {//head表示单链表的头，默认值为null,因为此时head这个头指针不指向我们的头节点public Node head;//在进行头插法之前，首先要进行链表的创建//其次在创建的过程中，我们还要将获取到的头节点的地址赋值给headpublic void createLinkList() {//将第一个节点的地址赋给我们headthis.head = new Node(10);Node node2 = new Node(20);Node node3 = new Node(30);Node node4 = new Node(40);Node node5 = new Node(50);this.head.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;}//遍历输出链表public void display() {Node cur = this.head;while (cur != null) {System.out.println(cur.data);cur = cur.next;}System.out.println();}//通过遍历，找到链表最后一个节点//注意要考虑到链表为空的情况public Node findLastNode() {if (this.head == null) {System.out.println("链表是空的，根本没有最后一个节点");return null;}Node cur = this.head;while (cur.next != null) {cur = cur.next;}return cur;}//通过遍历，找到链表的倒数第二个节点//注意要考虑到只有一个节点和链表为空的情况public Node findLastTwoNode() {if (this.head.next == null) {System.out.println("只有一个节点");return null;}if (this.head == null) {System.out.println("一个节点都没有");return null;}Node cur = this.head;while (cur.next.next != null) {cur = cur.next;}return cur;}//得到单链表的长度public int size() {int count = 0;Node cur = this.head;if (cur == null) {return -1;}while (cur != null) {cur = cur.next;count++;}return count;}//找到链表的第n个节点//同样需要判断链表为空和所找的第n个节点是否超过了当前链表的长度public Node findNumber(int n) {if (this.head == null) {System.out.println("一个节点都没有");return null;}if (n <= 0) {System.out.println("根本不存在这个节点");return null;}if (n > size()) {System.out.println("所要找的节点超过了链表的长度");return null;}Node cur = this.head;int count = 1;while (count != n) {cur = cur.next;count++;}return cur;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key) {Node cur = this.head;while (cur != null) {if (cur.data == key) {return true;}cur = cur.next;}//找不到返回falsereturn false;}//头插法非优化方法/*分为三步：第一步：首先的有一个节点第二步：判断链表是否为空第三步：如果不为空，进行插入*/public void addFirst(int data) {//创建一个要插入的节点，其next域默认为nullNode node = new Node(data);if (this.head == null) {this.head = node;} else {//注意在任何情况下往链表里面插入数据的时候，先绑定后面，node.next = this.head;this.head = node;}}//头插法的优化public void addFirst1(int data) {//创建一个要插入的节点，其next域默认为nullNode node = new Node(data);//优化之后可以去掉判断空的情况node.next = this.head;this.head = node;}//尾插法非优化方法/*1：创造一个要插入的节点2：判断此时要插入的链表是否为空，如果为空，就直接插入3：非空的话就正常插入*/public void addLast(int data) {Node node = new Node(data);if (this.head == null) {this.head = node;} else {//获取到当前非空链表的头节点Node cur = this.head;while (cur.next != null) {cur = cur.next;}cur.next = node;}}//该函数是为了找到index-1位置的节点的引用//index是下标的意思，第三个节点的index值为2//由于链表底部不是数组，没有下标，所以这个下标是我们自己定义的，方便我们自己使用//例如此时我要在第三个节点处插入数据，此时这个节点index=2//在第三个节点插入数据，就应该去寻找第二个节点是谁，而第二个节点的index=1//所以说moveIndex方法的目标是寻找到所插入节点的位置的前一节点public Node moveIndex(int index) {if (index <= 1) {System.out.println("寻找的位置出错");return null;}if (index > size() + 1) {System.out.println("所找的位置大了");return null;}Node cur = this.head;int count = 0;while (count != index - 1) {cur = cur.next;count++;}return cur;}//任意位置插入,第一个数据节点为0号下标//注意插入的时候不管什么插入，一定是先考虑后面插入，在考虑前面插入public void addIndex(int index, int data) {if (index < 0 || index > size()) {System.out.println("所插入的位置不合法");/*return;这个语句一般出现在一个无返回值的函数里面，函数里面可以有很多行，有的时候需要程序运行到某一行就要停止退出本函数，就需要用到return;语句*/return;}//index=0的时候为头插法if (index == 0) {addFirst1(data);return;}//index等于链表长度的时候为尾插法if (index == size()) {addLast(data);return;}//创建一个要插入的新的节点Node node = new Node(data);//查找到要插入的节点位置的前一节点Node cur = moveIndex(index);node.next = cur.next;cur.next = node;}//删除第一次出现关键字为key的节点/*1：首先需要判断所删除的节点是否存在于链表中,可根据所要删除节点的前驱节点是否存在来判断如果存在，说明在链表中，反之亦然。2: 还要判断链表是否为空，如果为空，那么直接执行return;语句3：如果存在于链表中，那么就去找所要删除节点的前驱4：假设我们要删除的节点为del,此节点的前驱为cur,那么删除del这个节点的核心语句为cur.next=del.next5：当删除的节点为首节点的时候，首节点是没有前驱的,cur不存在所以必须进行独立的判断：if(this.head.data==key){this.head=this.head.next;}*/public void remove(int key) {//判断链表是否为空if (this.head == null) {return;}if (this.head.data == key) {this.head = this.head.next;return;}//找到所要删除的节点的前驱节点Node pre = searchPre(key);//如果找不到所要删除的节点的前驱节点，说明要删除的这个节点根本不存在if (pre == null) {System.out.println("根本没有这个节点的前驱");} else {//将所找到的key值对应的节点赋给cur这个引用Node cur = pre.next;pre.next = cur.next;}}//找到存储关键字key这个节点的前驱节点/*找到关键key的前驱，如果有返回前驱节点的引用如果没有返回null*/public Node searchPre(int key) {Node cur = this.head;//注意循环条件为cur.next,如果是cur，相当于遍历完成，但是尾结点不可能是其他节点的前驱，//所以此处应该是走到最后一个节点时循环就应该终止了。while (cur.next != null) {if (cur.next.data == key) {return cur;}cur = cur.next;}return null;}//清空链表public void clear() {this.head = null;}public static void main(String[] args) {}public static void main1(String[] args) {//new Node()代表实例化了一个节点对象，其地址存储在node这个引用当中Node node = new Node();System.out.println(node.data);System.out.println(node.next);System.out.println("=========");Node node1 = new Node(10);System.out.println(node1.data);System.out.println(node1.next);}}

顺序表和链表的区别