简介
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;
}
本文的代码地址:
learn-algorithm
本文收录于 http://www.flydean.com/algorithm-linked-list/
最艰深的解读,最粗浅的干货,最简洁的教程,泛滥你不晓得的小技巧等你来发现!
欢送关注我的公众号:「程序那些事」, 懂技术,更懂你!