看动画学算法之Java实现doublyLinkedList

看动画学算法之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 = 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指向null

newNode.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指向prevNode

newNode.prev = prevNode;

//newNode的下一个节点的prev指向newNode

if (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 && i

temp = temp.next;

// 如果超出范围

if (temp == null || temp.next == null)

return;

// temp->next 是要删除的节点，删除节点

Node next = temp.next.next;

temp.next = next;

Node prev = temp.next.prev;

prev.prev = prev;

}

temp = temp.next;

// 如果超出范围

if (temp == null || temp.next == null)

return;

// temp->next 是要删除的节点，删除节点

Node next = temp.next.next;

temp.next = next;

Node prev = temp.next.prev;

prev.prev = prev;

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。