如何学linkedList算法

125次阅读

没有评论

共计 2130 个字符，预计需要花费 6 分钟才能阅读完成。

这篇文章将为大家详细讲解有关如何学 linkedList 算法，文章内容质量较高，因此丸趣 TV 小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。

简介

linkedList 应该是一种非常非常简单的数据结构了。节点一个一个的连接起来，就成了 linkedList。今天我们使用动画的方法一起来看看 linkedList 是怎么插入和删除的。

linkedList 的构建

linkedList 是由一个一个的节点构成的。而每个节点只需要存储要保存的数据和下一个节点的引用即可。

linkedList 本身需要一个 head 节点，所以我们的 linkedList 可以这样构建：

public class LinkedList {
 Node head; // head  节点
 //Node 表示的是 Linked list 中的节点，包含一个 data 数据和下一个节点的引用
 class Node {
 int data;
 Node next;
 //Node 的构造函数
 Node(int d) {
 data = d;
 }
 }
}

linkedList 的操作

先看一下 linkedList 怎么插入数据，插入数据有三种方式，头部插入，尾部插入，中间插入。

头部插入

先看一个头部插入的例子：

头部插入的逻辑是什么呢？

新插入的节点作为 head 节点，然后将原来的 head 节点指向当前 head 节点的 next 引用即可。

// 插入到 linkedList 的头部
 public void push(int newData) {
 // 构建要插入的节点
 Node newNode = new Node(newData);
 // 新节点的 next 指向现在的 head 节点
 newNode.next = head;
 // 现有的 head 节点指向新的节点
 head = newNode;
 }

尾部插入

再看一下尾部插入的例子：

插入的逻辑是什么呢？

找到最后一个节点，然后将最后一个节点的 next 指向新插入的节点。

// 新节点插入到 list 最后面
 public void append(int newData) {
 // 创建新节点
 Node newNode = new Node(newData);
 // 如果 list 是空，则新节点作为 head 节点
 if (head == null) {
 head = newNode;
 return;
 }
 newNode.next = null;
 // 找到最后一个节点
 Node last = head;
 while (last.next != null) {
 last = last.next;
 }
 // 插入
 last.next = newNode;
 return;
 }

中间插入

再看一下中间插入的例子：

这个例子中，我们在第三个节点的位置插入了一个 93。

插入逻辑就是先找到第二个节点，将第二个节点的 next 指向新节点，然后将新节点的 next 指向原先的第三个节点。

看下 java 代码如何实现：

// 插入在第几个元素之后
 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;
 }

删除节点

再看一下怎么删除某个位置的节点：

上面的例子中，我们要删除第 5 个节点。

删除的逻辑就是找到第 4 个节点和第 6 个节点。然后将第四个节点的 next 指向第 6 个节点即可。

看下相应的 java 代码如下：

// 删除特定位置的节点
 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 index-1; i++)
 temp = temp.next;
 //  如果超出范围
 if (temp == null || temp.next == null)
 return;
 // temp- next  是要删除的节点，删除节点
 Node next = temp.next.next;
 temp.next = next;
 }

关于如何学 linkedList 算法就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。

正文完