java数据结构基础:单|java数据结构基础:单,双向链表
目录
- 单向链表
- 单链表图解
- 代码
- 双向链表
- 编码
- 总结
单向链表 单向链表比顺序结构的线性表最大的好处就是不用保证存放的位置,它只需要用指针去指向下一个元素就能搞定。
单链表图解
文章图片
图画的比较粗糙,简单的讲解一下:
上面四个长方形,每个长方形都是一个节点。在长方形中,一种包含两个东西,一个是当前节点的元素,一个是指向下一节点的地址。这个下一个节点的地址指向了下一个节点中的元素。以此类推。
在最左边的叫做头节点,同样,最后面的叫尾节点。
【java数据结构基础:单|java数据结构基础:单,双向链表】所以,我们所有的操作都是根据节点来进行操作。
代码
这些代码都有很详细的注释,我就不做过多的解释了,你直接复制代码到本地idea运行一遍就全部知道了。
package com.zxy.lianbiao; /** * @Author Zxy * @Date 2021/2/3 21:25 * @Version 1.0 *//** * 基于单向链表实现元素的存取 * * @param*/public class MySinglyLinkedList implements MyList {/*** 定义单向链表中的节点对象*/class Node {private E item; // 存储元素private Node next; // 存储下一个节点对象public Node(E item, Node next) {this.item = item; this.next = next; }}private Node head; // 存放链表中的头节点private int size; // 记录元素的个数/*** 向链表中添加元素** @param element*/@Overridepublic void add(E element) {// 创建节点Node node = new Node<>(element, null); // 找到尾节点Node tail = getTail(); // 节点的挂接if (tail == null) { // 如果没有尾节点,那意思就是头节点都不存在// 没有头节点,那么就把创建的节点给头节点this.head = node; } else {tail.next = node; }// 记录元素的个数this.size++; }/*** 找尾节点*/private Node getTail() {// 判断头节点是否存在if (this.head == null) {return null; }// 查找尾节点Node node = this.head; while (true) {if (node.next == null) {break; }node = node.next; // 移动指针指向下一个}return node; }/*** 根据元素的位置获取元素** @param index* @return*/@Overridepublic E get(int index) {// 校验index的合法性this.checkIndex(index); // 根据位置获取指定节点Node node = this.getNode(index); // 将该节点中的元素返回return node.item; }/*** 对index进行校验*/private void checkIndex(int index) {// 0<=index= 0 && index < this.size)) {throw new IndexOutOfBoundsException("Index: " + index + "this.size: " + this.size); }}/*** 根据位置获取节点*/private Node getNode(int index) {Node node = this.head; for (int i = 0; i < index; i++) {node = node.next; }return node; }/*** 获取元素的个数** @return*/@Overridepublic int size() {return this.size; }/*** 根据元素位置删除元素** @param index* @return*/@Overridepublic E remove(int index) {// 校验index合法性this.checkIndex(index); // 根据位置找到节点对象Node node = getNode(index); // 获取该节点对象中的元素E item = node.item; // 将该节点对象从单向链表中移除// 判断当前删除的节点是否为头节点if (this.head == node) {this.head = node.next; } else {Node temp = this.head; for (int i = 0; i < index - 1; i++) {temp = temp.next; // 此时的temp就是要删除的那个节点的前一个节点}temp.next = node.next; // 将当前节点的前一个节点指向当前节点的后一个节点}// 然后将当前节点的下一个节点指向nullnode.next = null; // 记录元素个数this.size--; // 将该元素返回return item; }/*** 插入节点思路:如果当前共有三个节点分别是1,2,3,在1和2的中间插入4,原本的指向是1->2 现改变成1->4 4->2 先获取到指定位置的node,再获取到前一个位置的node和下一个位置的node*/public void insert(int index, E element) {// 先根据要插入的位置拿到这个位置的节点对象Node item = getNode(index); // 根据插入的元素新建一个节点Node eNode = new Node<>(element, null); // 如果是头节点,那么就找不到前一个,直接把这个赋值给headif (index == 0){// index==0代表是替换掉头节点this.head = eNode; eNode.next = item; this.size++; }else {// 根据当前的节点对象去找到前一个节点对象和后一个节点对象Node before = this.head; // 根据头节点去找for (int i = 0; i < index - 1; i++) {before = before.next; // 此时的before就是当前节点的前一个节点}before.next = eNode; eNode.next = item; this.size++; }}public static void main(String[] args) {MySinglyLinkedList list = new MySinglyLinkedList<>(); System.out.println("添加节点开始------------------------"); list.add((String) "a"); list.add((String) "b"); list.add((String) "c"); list.add((String) "d"); System.out.println("添加节点完成-------------------------\n"); System.out.println("插入指定的元素"); list.insert(0,"f"); for (int i = 0; i < list.size; i++) {System.out.println(list.get(i)); }}}
双向链表 昨天写完单向链表和栈结构之后,看了看程杰大大的书中有介绍双向链表的部分。虽然是c语言写的,但是我还是用Java给翻译出来了。
思路如下:
首先,双向链表和单向链表的最大区别就是,双向链表比单链表多了个指向前一节点的指针。代码量其实并不比单链表多很多,只是思路的转变需要克服一下。
其次就是在插入元素的时候,我们可以在链表的头部插入,也可以在链表的尾部插入(因为有两个指针嘛)
编码
代码其实和单链表差不多,如果感兴趣的话可以去看看我之前写的单链表的文章。虽然文笔很烂,但是代码货真价实。
package com.zxy.lianbiao; /** * @Author Zxy * @Date 2021/2/4 20:11 * @Version 1.0 *//** * 基于双向链表实现元素存取的容器 * * @param*/public class MyDoublyLinkedList implements MyList {/*** 定义双向链表节点对象*/class Node {E item; // 记录元素Node prev; // 记录前一个节点对象Node next; // 记录下一个节点对象public Node(Node prev, E item, Node next) {this.item = item; this.prev = prev; this.next = next; }}private Node head; // 记录头节点private Node tail; // 记录尾节点private int size; // 记录元素个数/*** 向双向链表中添加元素的方法** @param element*/@Overridepublic void add(E element) {linkLast(element); }/*** 将节点对象添加到双向链表的尾部*/private void linkLast(E element) {Node t = this.tail; // 获取尾节点Node node = new Node<>(t, element, null); // 创建节点对象this.tail = node; // 将新节点定义为尾节点 因为原来的尾节点被这个新节点替代了if (t == null) {// 说明一个节点都没有,这个还得是头节点this.head = node; } else {t.next = node; }this.size++; }/*** 根据指定位置获取元素** @param index* @return*/@Overridepublic E get(int index) {this.checkIndex(index); // 根据位置查找节点对象Node node = this.getNode(index); return node.item; }/*** 对index的合法性校验*/private void checkIndex(int index) {if (!(index >= 0 && index < this.size)) {throw new IndexOutOfBoundsException(); }}/*** 根据位置获取指定节点对象*/private Node getNode(int index) {// 判断当前位置距离头或者尾哪个节点更近使用二分法if (index < (this.size >> 1)) {Node node = this.head; for (int i = 0; i < index; i++) {node = node.next; }return node; } else {Node node = this.tail; for (int i = this.size - 1; i > index; i--) {node = node.prev; }return node; }}/*** 返回元素的个数** @return*/@Overridepublic int size() {return this.size; }/*** 删除元素** @param index* @return*/@Overridepublic E remove(int index) {// 对index进行合法性校验this.checkIndex(index); Node node = this.getNode(index); // 根据位置获取到节点对象// 获取节点对象的元素E item = (E) node.item; // 判断当前节点是否为头节点if (node.prev == null) {this.head = node.next; } else {node.prev.next = node.next; }// 判断当前节点是否为尾节点if (node.next == null) {// node.prev.next = null; this.tail = node.prev; } else {node.next.prev = node.prev; }// 当前节点断掉与他后继节点的连接node.next = null; // 当前节点断掉与直接前驱节点的连接node.prev = null; node.item = null; this.size--; return item; }/*** 在双向链表的头添加元素*/public void addFirst(E element) {this.linkFirst(element); }/*** 在链表的头添加元素** @param element*/public void linkFirst(E element) {// 获取头节点对象Node head = this.head; Node eNode = new Node<>(null, element, head); // 将新节点定义为头节点this.head = eNode; if (head == null) {// 如果为空,说明该链表中一个节点都没有 也就是该头节点也是尾节点this.tail = eNode; } else {head.prev = eNode; }this.size++; }/*** 在链表的尾部添加元素** @param element*/public void addLast(E element) {this.linkLast(element); }public static void main(String[] args) {MyDoublyLinkedList list = new MyDoublyLinkedList<>(); list.add("a"); list.add("b"); list.add("c"); list.add("d"); list.add("e"); System.out.println(list.remove(2)); System.out.println(list.size); for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i)); }}}
总结 本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注脚本之家的更多内容!
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 事件代理
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树
- 数组常用方法一
- Python基础|Python基础 - 练习1
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- Java|Java基础——数组
- RxJava|RxJava 在Android项目中的使用(一)
- java之static、static|java之static、static final、final的区别与应用