链表的定义
链表就像每个节点串起来一样构成了一串，每个节点都是一个节点对象
其中我们对于每个节点会去划分域，分为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 2021/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; //在进行头插法之前，首先要进行链表的创建 //其次在创建的过程中，我们还要将获取到的头节点的地址赋值给head public void createLinkList() { //将第一个节点的地址赋给我们head this.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; } //找不到返回false return false; } //头插法非优化方法 /* 分为三步： 第一步：首先的有一个节点 第二步：判断链表是否为空 第三步：如果不为空，进行插入 */ public void addFirst(int data) { //创建一个要插入的节点，其next域默认为null Node 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域默认为null Node 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.next 5： 当删除的节点为首节点的时候，首节点是没有前驱的,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); } }
顺序表和链表的区别
