行业知识
Java链表入门(超详细)
Java链表入门 超详细
- 什么是链表
- 创建链表
- 1. 创建一个结点
- 2. 插入一个结点
- -- 头插
- -- 尾插
- -- 指定位置插入
- 3.查找是否包含关键字key是否在单链表当中
- 4.删除元素
- --删除第一次出现关键字为key的节点
- --删除所有值为key的节点
- 4.得到单链表的长度
- 5.清空链表
- 6.打印链表
- 7.反转链表
- 8.返回中间结点
- 9.创建一个链表
- 无头结点单向链表
- 双向循环链表
- Java标准库中的链表
- LinkedList 和 ArrayList 的区别
什么是链表
说起链表,可以说是让刚接触数据结构的同学非常懵逼的
那么什么是链表呢??
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。
那么这是链表吗,是的,但是究竟是什么意思呢
其实,链表就像是解密游戏一样,只有到达一个地点,才会有NPC给你下一个地点的地图,从而才能知道下个地点的位置
所以链表也是一样,对于一个链表,一个结点除了要保存结点自身的值以外,还需要保存下一个结点的地址.
这是一个简单链表的单个结点,val代表当前结点存储的值,next是一个引用,指向下一个结点
由于Java中不存在指针,所以结点通常为一个类,而next则是一个结点类实例的引用
可以看到,每一结点都保存了下一个节点的地址,所以,链表不要求每个结点中的地址空间连续
创建链表
–> 怎么创建一个链表呢 //值public int value;// Node 节点类型,引用当前结点的下一个结点public Node next; //构造方法初始化/** * @param value 值 */ public Node(int value){ this.value = value; next = null; }}} //尾插法 public void addLast(int value){} //任意位置插入,第一个数据节点为0号下标 public boolean addIndex(int index,int value){return false;} //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){return false;} //删除第一次出现关键字为key的节点 public void remove(int key){} //删除所有值为key的节点 public void removeAllKey(int key){} //得到单链表的长度 public int size(){return -1;} public void display(){} public void clear(){} Node node = new Node(0); Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); //创建一个链表 head = node; node.next = node1; node1.next = node2; node2.next = node3; node3.next = node4; } //根据值创建新结点 Node node = new Node(val); //判断链表是否为空 if(size == 0){ this.head = node; }else { //链表不为空 node.next = head; head = node; } //元素个数+1 this.size++; } //根据值创建新结点 Node node = new Node(val); //判断链表是否为空 if (size == 0) { this.head = node; } else { //链表不为空 //创建临时变量记录头结点,防止遍历后找不到头结点 Node tmpHead = head; Node cur = tmpHead.next; while (cur != null) { tmpHead = cur; cur = cur.next; } // 循环结束后,tmpHead为最后一个结点 tmpHead.next = node; } this.size++; } //判断index是否合理 if(index 1){ tmpHead = tmpHead.next; index--; } node.next = tmpHead.next; tmpHead.next = node; this.size++; return true; }
插入操作到此结束
3.查找是否包含关键字key是否在单链表当中
遍历链表,按个查找即可
//查找是否包含关键字key是否在单链表当中 public boolean contains(int key) { //记录头结点 Node next = this.head; //遍历每一个结点 while (next != null) { //如果找到,返回true if (next.value == key) { return true; } next = next.next; } //未找到,返回 false return false; }4.删除元素
–删除第一次出现关键字为key的节点
关键之处在于
node = next;
next = next.next;
//删除第一次出现关键字为key的节点 public void remove(int key) { if (!contains(key)) { System.out.println("没有该元素"); } Node next = this.head; Node node = next; //判断第一个元素 if (next.value == key) { this.head = next.next; next.next = null; this.size--; return; } //循环判断后续元素 while (next != null) { if (next.value == key) { //跳过中间元素 node.next = next.next; //置空 next.next = null; //元素减一 this.size--; return; } //让 next 始终在 node 的下一个元素 node = next; next = next.next; } }–删除所有值为key的节点
与删除一个元素不同的是,删除所有key值元素在循环判断时找到指定元素时不退出,继续进行查找,直到链表遍历完成.
//删除所有值为key的节点 public void removeAllKey(int key) { if (this.head == null) { return; } Node cur = this.head.next; Node pre = this.head; //遍历整个链表,判断每个元素 while (cur != null) { if (cur.value == key) { // 跳过 指定元素 pre.next = cur.next; } else { pre = cur; } cur = cur.next; } /* Node cur = this.head.next; Node pre = this.head; 上述代码跳过了head.value 所以需要单独判断 */ if (this.head.value == key) { this.head = this.head.next; } }4.得到单链表的长度
//得到单链表的长度 public int size() { return this.size; }5.清空链表
直接使用 this.head = null;可以达到一样的效果,但此处对每个结点引用置空.
public void clear() { this.size = 0; Node tmp; while (head.next != null) { tmp = this.head.next; //置空 head.next = null; head = tmp; } this.head = null; }6.打印链表
//打印链表 public void display() { Node tmp = this.head; System.out.print("["); while (tmp != null) { if (tmp.next == null) System.out.print(tmp.value); else System.out.print(tmp.value + ","); tmp = tmp.next; } System.out.println("]"); }7.反转链表
反转链表的核心在于,需要一个pre记录下一个结点是否为空,因为在程序运行过程中,cur会断开与下一个节点的连接,所以需要单独添加引用记录.
//反转链表 public Node reverse() { if (this.size == 0) { return null; } if (head.next == null) { return head; } Node cur = head.next; head.next = null; //pre记录下一个元素 Node pre; while (cur != null) { pre = cur.next; cur.next = head; head = cur; cur = pre; } return head; }8.返回中间结点
采用快慢指针的思想,慢指针一次移动一步,快指针一次移动2步,当快指针移动到链表末尾时,慢指针就在链表中间位置
//返回中间结点 public Node middleNode() { Node fast = head; Node slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; }9.创建一个链表
传入一个数组快速创建一个链表,实际中,根据情况做判断.
//创建一个链表public void create(int[] arr){ if(this.head != null){ System.out.println("链表不为空!"); } Node tmp = null; for (int i = 0; i到这里为止,关于链表的基本操作就结束了…
下面是整个源码.
对于链表,以上演示的是无头单向不循环链表,对应的还有很多的不同实现的链表,如,有头双向循环链表
对于循环链表,就是每一个结点都记录了前后2个节点的引用,
对于双向链表,就是除了头结点外,还记录了尾节点.
无头结点单向链表
//无头结点单向链表public class LinkedList { //结点类 private static class Node { public int value; public Node next; public Node(int value) { this.value = value; next = null; } } //指定头结点为空 private Node head = null; private int size = 0; public void createLinkedList() { Node node = new Node(0); Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); //创建一个链表 head = node; node.next = node1; node1.next = node2; node2.next = node3; node3.next = node4; size = 5; } //头插法 public void addFirst(int val) { //根据值创建新结点 Node node = new Node(val); //判断链表是否为空 if (size == 0) { this.head = node; } else { //链表不为空 node.next = head; head = node; } this.size++; } //尾插法 public void addLast(int val) { //根据值创建新结点 Node node = new Node(val); //判断链表是否为空 if (size == 0) { this.head = node; } else { //链表不为空 //创建临时变量记录头结点,防止遍历后找不到头结点 Node tmpHead = head; Node cur = tmpHead.next; while (cur != null) { tmpHead = cur; cur = cur.next; } // 循环结束后,tmpHead为最后一个结点 tmpHead.next = node; } this.size++; } //任意位置插入,第一个数据节点为0号下标 public boolean addIndex(int index, int val) { //判断index是否合理 if (index this.size) { System.out.println("输入下标不合理..."); return false; } Node node = new Node(val); Node tmpHead = this.head; //如果index为0进行头插 if (index == 0) { node.next = head; head = node; return true; } //循环结束后,tmpHead 在待插入位置的前一个位置 while (index > 1) { tmpHead = tmpHead.next; index--; } node.next = tmpHead.next; tmpHead.next = node; this.size++; return true; } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key) { //记录头结点 Node next = this.head; //遍历每一个结点 while (next != null) { //如果找到,返回true if (next.value == key) { return true; } next = next.next; } //未找到,返回 false return false; } //删除第一次出现关键字为key的节点 public void remove(int key) { if (!contains(key)) { System.out.println("没有该元素"); } Node next = this.head; Node node = next; //判断第一个元素 if (next.value == key) { this.head = next.next; next.next = null; this.size--; return; } //循环判断后续元素 while (next != null) { if (next.value == key) { //跳过中间元素 node.next = next.next; //置空 next.next = null; //元素减一 this.size--; return; } //让 next 始终在 node 的下一个元素 node = next; next = next.next; } } //删除所有值为key的节点 public void removeAllKey(int key) { if (this.head == null) { return; } Node cur = this.head.next; Node pre = this.head; //遍历整个链表,判断每个元素 while (cur != null) { if (cur.value == key) { // 跳过 指定元素 pre.next = cur.next; } else { pre = cur; } cur = cur.next; } /* Node cur = this.head.next; Node pre = this.head; 上述代码跳过了head.value 所以需要单独判断 */ if (this.head.value == key) { this.head = this.head.next; } } //得到单链表的长度 public int size() { return this.size; } //打印链表 public void display() { Node tmp = this.head; System.out.print("["); while (tmp != null) { if (tmp.next == null) System.out.print(tmp.value); else System.out.print(tmp.value + ","); tmp = tmp.next; } System.out.println("]"); } //清空链表 public void clear() { this.size = 0; Node tmp; while (head.next != null) { tmp = this.head.next; head.next = null; head = tmp; } this.head = null; } //反转链表 public Node reverse() { if (this.size == 0) { return null; } if (head.next == null) { return head; } Node cur = head.next; head.next = null; //pre记录下一个元素 Node pre; while (cur != null) { pre = cur.next; cur.next = head; head = cur; cur = pre; } return head; } //返回中间结点 public Node middleNode() { Node fast = head; Node slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; } public void create(int[] arr){ if(this.head != null){ System.out.println("链表不为空!"); } Node tmp = null; for (int i = 0; i双向循环链表
public class MyDoubleLinkedList { static private class Node { public int val; //记录前一个结点 public Node pre; //记录后一个结点 public Node next; public Node(int val) { this.val = val; this.pre = null; this.next = null; } }//记录头结点 private Node head; //记录尾结点 private Node last; //头插法 public void addFirst(int val) { Node tmp = new Node(val); if (head == null) { head = tmp; last = head; } else { tmp.next = head; head.pre = tmp; head = tmp; } } //尾插法 public void addLast(int val) { Node tmp = new Node(val); if (head == null) { head = tmp; last = head; } else { last.next = tmp; tmp.pre = last; last = tmp; } } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index, int val) { if (index size()) { System.out.println("下标越界"); } Node tmp = new Node(val); Node next = head; if(head == null){ head = tmp; last = tmp; return; } if (index == 0) { tmp.next = head; head.pre = tmp; head = tmp; return; } if (index == size()) { last.next = tmp; tmp.pre = last; last = tmp; return; } while (index > 0) { next = next.next; index--; } next.pre.next = tmp; tmp.next = next; tmp.pre = next.pre; next.pre = tmp; } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key) { Node next = head; while (next != null) { if (next.val == key) { return true; } next = next.next; } return false; } //删除第一次出现关键字为key的节点 public boolean remove(int key) { if(head == null || head.next == null){ head = null; return true; } if(head.val == key){ head = head.next; head.pre = null; return true; } Node tmp = head; while (tmp.val != key){ tmp = tmp.next; if(tmp == null){ return false; } } if(tmp == last){ last.pre.next = null; return true; } tmp.pre.next = tmp.next; tmp.next.pre = tmp.pre; return true; } //删除所有值为key的节点 public void removeAllKey(int key) { boolean b = true; while (b){ b = false; boolean remove = remove(key); if(remove) b = true; } } //得到单链表的长度 public int size() { int size = 0; Node next = head; while (next != null) { next = next.next; size++; } return size; } public void display() { Node next = head; System.out.print("["); while (next != null) { System.out.print(next.val + " "); next = next.next; } System.out.println("]"); } public void clear() { while (head.next != null){ head = head.next; head.pre = null; } head = null; last = null; }}Java标准库中的链表
在Java标准库中,内置了一个双向链表LinkedList类
方法 解释 boolean add(E e) 尾插 e void add(int index, E element) 将 e 插入到 index 位置 boolean addAll(Collection
上一篇:怎么把网页放到域名里