链表的顶级理解
目录
1.链表的概念及结构
2.链表的分类
单向或者双向
带头或者不带头
循环或者非循环
3.无头单向非循环链表的实现
3.1创建单链表
3.2遍历链表
3.3得到单链表的长度
3.4查找是否包含关键字
3.5头插法
3.6尾插法
3.7任意位置插入
3.8删除第一次出现关键字为key的节点
3.9回收链表
3.10完整代码
1.链表的概念及结构
概念:
链表是一种 物理存储结构上非连续 存储结构，数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。
结构:
实际在内存中每个节点的地址是随机的，只不过用这个节点的next,找到了下一个节点的地址，实现链接。
2.链表的分类
实际中链表的结构非常多样
以下情况组合起来就有8种链表结构：
单向或者双向
带头或者不带头
循环或者非循环
我们重点掌握无头单向非循环链表，这种结构在笔试面试中出现很多。并且可以触类旁通其他结构。
3.无头单向非循环链表的实现
链表的功能与顺序表类似，无非是增删查改，在某位置的插入与删除，对数据内容进行管理和操作。
具体实现内容：
（1）创建单链表（2）遍历链表（3）得到单链表的长度（4）查找是否包含关键字（5）头插法（6）尾插法（7）任意位置插入（8）删除第一次出现关键字为key的节点（9）回收链表
3.1创建单链表
public class MyLinkedList {class Node {public int val;public Node next;public Node(int val) {this.val = val;}}public Node head;// 代表当前链表的头节点的引用
}3.2遍历链表
public void disPlay() {Node sur = head;while(sur != null) {System.out.print(sur.val+" ");sur = sur.next;}}
3.3得到单链表的长度
进行遍历，并进行记录，最后进行返回就行
public int size(){int count = 0;Node cur = head;while (cur != null) {count++;cur = cur.next;}return count;}3.4查找是否包含关键字
对链表进行遍历，然后一一比
//查找是否包含关键字key是否在单链表当中public boolean contains(int key){Node cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}
3.5头插法
将第一个节点的地址赋给我们新添加的节点的next，并且将新添加的节点赋给head，作为新的头节点
public void addFirst(int data){Node node = new Node(data);node.next = head;head = node;}
3.6尾插法
首先对该链表进行遍历，当遍历到最后一个节点时，将新添加的节点的地址最后一个节点的next。
如果该链表为空，直接将该新增节点设为头节点
public void addLast(int data){Node node = new Node(data);if(head == null) {head = node;return;}Node cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}
3.7任意位置插入
需要插入的位置必须为合法，如果不合法，我们会抛出一个异常进行提醒
public class ListIndexOutOfException extends RuntimeException{public ListIndexOutOfException() {}public ListIndexOutOfException(String message) {super(message);}
}任意位置插入，我们可以分为种情况，插在开头，插在结尾，插在中间
插在结尾和插在中间可以总结成一种
//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data)throws ListIndexOutOfException{checkIndex(index);if(index == 0) {addFirst(data);return;}Node cur = findIndexSubOne(index);Node node = new Node(data);node.next = cur.next;cur.next = node;}/*** 找到 index-1位置的节点的地址* @param index* @return*/private Node findIndexSubOne(int index) {Node cur = head;int count = 0;while (count != index-1) {cur = cur.next;count++;}return cur;}private void checkIndex(int index) throws ListIndexOutOfException{if(index < 0 || index > size()) {throw new ListIndexOutOfException("index位置不合法");}}
3.8删除第一次出现关键字为key的节点
分为四种情况
（1）一个节点都没有
（2）删除数据在第一个
（3）没有你要删除的数据
（4）有你要删除的数据且不是第一个
//删除第一次出现关键字为key的节点 O(N)public void remove(int key)throws ListIndexOutOfException{checkIndex(key);if(head == null) {return ;//一个节点都没有}//删除数据在第一个if(head.val == key) {head = head.next;return;}Node cur = searchPrev(key);//没有你要删除的数据if(cur == null) {return;}Node del = cur.next;//要删除的节点cur.next = del.next;}/*** 找到关键字key的前一个节点* @param key* @return*/private Node searchPrev(int key) {Node cur = head;while (cur.next != null) {if(cur.next.val == key) {return cur;}cur = cur.next;}return null;//没有你要删除的节点}
3.9回收链表
将头节点置为空
public void clear() {head = null;}
3.10完整代码
public class MyLinkedList {class Node {public int val;public Node next;public Node(int val) {this.val = val;}}public Node head;// 代表当前链表的头节点的引用public void disPlay() {Node sur = head;while(sur != null) {System.out.print(sur.val+" ");sur = sur.next;}}public int size(){int count = 0;Node cur = head;while (cur != null) {count++;cur = cur.next;}return count;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){Node cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}public void addFirst(int data){Node node = new Node(data);node.next = head;head = node;}public void addLast(int data){Node node = new Node(data);if(head == null) {head = node;return;}Node cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data)throws ListIndexOutOfException{checkIndex(index);if(index == 0) {addFirst(data);return;}Node cur = findIndexSubOne(index);Node node = new Node(data);node.next = cur.next;cur.next = node;}/*** 找到 index-1位置的节点的地址* @param index* @return*/private Node findIndexSubOne(int index) {Node cur = head;int count = 0;while (count != index-1) {cur = cur.next;count++;}return cur;}private void checkIndex(int index) throws ListIndexOutOfException{if(index < 0 || index > size()) {throw new ListIndexOutOfException("index位置不合法");}}//删除第一次出现关键字为key的节点 O(N)public void remove(int key)throws ListIndexOutOfException{checkIndex(key);if(head == null) {return ;//一个节点都没有}//删除数据在第一个if(head.val == key) {head = head.next;return;}Node cur = searchPrev(key);//没有你要删除的数据if(cur == null) {return;}Node del = cur.next;//要删除的节点cur.next = del.next;}/*** 找到关键字key的前一个节点* @param key* @return*/private Node searchPrev(int key) {Node cur = head;while (cur.next != null) {if(cur.next.val == key) {return cur;}cur = cur.next;}return null;//没有你要删除的节点}public void clear() {head = null;}}
以上为我个人的小分享，如有问题，欢迎讨论！！！
都看到这了，不如关注一下，给个免费的赞 
