链表的顶级理解

目录

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;}}

---

以上为我个人的小分享，如有问题，欢迎讨论！！！ 

都看到这了，不如关注一下，给个免费的赞