看动画学算法之Java实现doublyLinkedList
简介:
和LinkedList
相比,doublyLinkedList
中的节点除了next指向下一个节点之外,还有一个prev
之前的一个节点。所以被称为doublyLinkedList。 doublyLinkedList
是一个双向链表,我们可以向前或者向后遍历list。
今天我们来学习一下doublyLinkedList
的基本操作和概念。
1、doublyLinkedList的构建
和linkedList
一样,doublyLinkedList
是由一个一个的节点构成的。而每个节点除了要存储要保存的数据之外,还需要存储下一个节点和上一个节点的引用。
文章图片
doublyLinkedList
需要一个head
节点,我们看下怎么构建:
public class DoublyLinkedList {Node head; // head 节点//Node表示的是Linked list中的节点,包含一个data数据,上一个节点和下一个节点的引用class Node {int data; Node next; Node prev; //Node的构造函数Node(int d) {data = https://www.it610.com/article/d; }}}
2、doublyLinkedList的操作 接下来,我们看一下
doublyLinkedList
的一些基本操作。2.1 头部插入
文章图片
头部插入的逻辑是:将新插入的节点作为新的
head
节点,并且将newNode.next
指向原来的head
节点。同时需要将
head.prev
指向新的插入节点。看下java代码:
//插入到linkedList的头部public void push(int newData) {//构建要插入的节点Node newNode = new Node(newData); //新节点的next指向现在的head节点//新节点的prev指向nullnewNode.next = head; newNode.prev = null; if (head != null)head.prev = newNode; //现有的head节点指向新的节点head = newNode; }
2.2 尾部插入
文章图片
尾部插入的逻辑是:找到最后一个节点,将最后一个节点的next指向新插入的节点,并且将新插入的节点的prev指向最后一个节点。
//新节点插入到list最后面public void append(int newData) {//创建新节点Node newNode = new Node(newData); //如果list是空,则新节点作为head节点if (head == null) {newNode.prev = null; head = newNode; return; }newNode.next = null; //找到最后一个节点Node last = head; while (last.next != null) {last = last.next; }//插入last.next = newNode; newNode.prev = last; return; }
2.3 插入给定的位置
文章图片
如果要在给定的位置插入节点,我们需要先找到插入位置的前一个节点,然后将前一个节点的
next
指向新节点。新节点的prev
指向前一个节点。同时我们需要将新节点的
next
指向下一个节点,下一个节点的prev
指向新的节点。//插入在第几个元素之后public void insertAfter(int index, int newData) {Node prevNode = head; for (int i = 1; i < index; i++) {if (prevNode == null) {System.out.println("输入的index有误,请重新输入"); return; }prevNode = prevNode.next; }//创建新的节点Node newNode = new Node(newData); //新节点的next指向prevNode的下一个节点newNode.next = prevNode.next; //将新节点插入在prevNode之后prevNode.next = newNode; //将新节点的prev指向prevNodenewNode.prev = prevNode; //newNode的下一个节点的prev指向newNodeif (newNode.next != null)newNode.next.prev = newNode; }
2.4 删除指定位置的节点
文章图片
删除节点的逻辑是:找到要删除节点的前一个节点,和下一个节点。前一个节点的
next
指向下一个节点,下一个节点的prev
指向前一个节点。//删除特定位置的节点void deleteNode(int index){// 如果是空的,直接返回if (head == null)return; // head节点Node temp = head; // 如果是删除head节点if (index == 1){head = temp.next; return; }// 找到要删除节点的前一个节点for (int i=1; temp!=null && inext 是要删除的节点,删除节点Node next = temp.next.next; temp.next = next; Node prev = temp.next.prev; prev.prev = prev; }
【看动画学算法之Java实现doublyLinkedList】到此这篇关于看动画学算法之Java实现
doublyLinkedList
的文章就介绍到这了,更多相关Java实现doublyLinkedList内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!推荐阅读
- 慢慢的美丽
- 一个小故事,我的思考。
- 第三节|第三节 快乐和幸福(12)
- 开学第一天(下)
- 死结。
- 奔向你的城市
- 学无止境,人生还很长
- 由浅入深理解AOP
- “成长”读书社群招募
- 拍照一年啦,如果你想了解我,那就请先看看这篇文章