作者:小傅哥 博客:https://bugstack.cn
❝沉淀、分享、成长,让自己和他人都能有所收获!😜 ❞
链表的历史
于1955-1956年,由兰德公司的Allen Newell、Cliff Shaw和Herbert A. Simon开发了链表,作为他们的信息处理语言的主要数据结构。链表的另一个早期出现是由 Hans Peter Luhn 在 1953 年 1 月编写的IBM内部备忘录建议在链式哈希表中使用链表。
到 1960 年代初,链表和使用这些结构作为主要数据表示的语言的实用性已经很好地建立起来。MIT 林肯实验室的 Bert Green于 1961 年 3 月在 IRE Transactions on Human Factors in Electronics 上发表了一篇题为“用于符号操作的计算机语言”的评论文章,总结了链表方法的优点。1964 年 4 月,Bobrow 和 Raphael 的一篇评论文章“列表处理计算机语言的比较”发表在 ACM 通讯中。
在计算机科学中,链表是数据元素的线性集合,元素的线性顺序不是由它们在内存中的物理地址给出的。它是由一组节点组成的数据结构,每个元素指向下一个元素,这些节点一起,表示线性序列。
在最简单的链表结构下,每个节点由数据和指针(存放指向下一个节点的指针)两部分组成,这种数据结构允许在迭代时有效地从序列中的任何位置插入或删除元素。
链表的数据结构通过链的连接方式,提供了可以不需要扩容空间就更高效的插入和删除元素的操作,在适合的场景下它是一种非常方便的数据结构。但在一些需要遍历、指定位置操作、或者访问任意元素下,是需要循环遍历的,这将导致时间复杂度的提升。
链表的主要表现形式分为;单向链表、双向链表、循环链表,接下来我们分别介绍下。
单链表包含具有数据字段的节点以及指向节点行中的下一个节点的“下一个”字段。可以对单链表执行的操作包括插入、删除和遍历。
在“双向链表”中,除了下一个节点链接之外,每个节点还包含指向序列中“前一个”节点的第二个链接字段。这两个链接可以称为'forward('s')和'backwards',或'next'和'prev'('previous')。
在列表的最后一个节点中,链接字段通常包含一个空引用,一个特殊的值用于指示缺少进一步的节点。一个不太常见的约定是让它指向列表的第一个节点。在这种情况下,列表被称为“循环”或“循环链接”;否则,它被称为“开放”或“线性”。它是一个列表,其中最后一个指针指向第一个节点。
像 Java 的源码中本身就提供了非常多的数据结构,包括我们所学习的链表 LinkedList 在日常的开发使用中也是非常频繁。
所以我们在学习的过程中,以使用 Java 程序员本身常用的语言来分析学习,并通过简化结构的方式把 LinkedList 手写实现,让读者更能方便的理解链表。
Java 算法与数据结构
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
public Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
size++;
}
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
return element;
}
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
public static void main(String[] args) {
List<String> list = new LinkedList<>();
// 添加元素
list.add("a");
list.addFirst("b");
list.addLast("c");
// 打印列表
list.printLinkList();
// 头插元素
list.addFirst("d");
// 删除元素
list.remove("b");
// 打印列表
list.printLinkList();
}
测试结果
目前的列表,头节点:b 尾节点:c 整体:b,a,c,
目前的列表,头节点:d 尾节点:c 整体:d,a,c,
Process finished with exit code 0
- END -
你好,我是小傅哥。一线互联网java
工程师、架构师,开发过交易&营销、写过运营&活动、设计过中间件也倒腾过中继器、IO板卡。不只是写Java语言,也搞过C#、PHP,是一个技术活跃的折腾者。