在谈链表之前，咱们先谈谈咱们平时编程会遇到的很常见的一个问题。如果在编程的时候，某个变量在后续编程中仍需应用，咱们能够用一个局部变量来保留该值，除此之外一个更加罕用的办法就是应用容器了。
那什么是容器呢？从字面上来说就是用来装某个货色的，比方咱们的杯子，就是容器。在程序设计当中咱们最常见的容器就是数组了，他能够存咱们想保留的货色。在编程当中咱们最常见的容器如下：
ArrayList、LinkedList、HashMap、HashSet等等。vector、list、unordered_map、unordered_set等等。明天要谈到的链表在Java的LinkedList和C++的list当中就有应用到。
那什么是链表呢？链表是由一个一个的节点组成的，每个节点蕴含两个字段，其中一个字段data示意实在须要示意的数据，另外一个字段next示意指向下一个节点的指针（如果不理解指针也没有关系，就将其当做一个一般的变量既可，不影响咱们的了解），data和next两者一起组成链表当中的节点(Node)。
其中data示意链表当中存储的实在的数据，而next示意指向下一个节点的指针（如果不理解指针也没有关系，就将其当做一个一般的变量既可，不影响咱们的了解），data和next两者一起组成链表当中的节点(Node)。
Java代码：
class Node {
E item;
Node next;
public Node(E item, Node next) {
this.item = item;
this.next = next;
}
} 所谓单链表就是只有一个指向其余节点的变量，比方下图当中只有一个next变量指向其余同样的节点。
双向链表和单链表的区别就是他的指向有两个方向，而单链表只有一个方向，在双向链表的节点当中会有两个指向其余同样节点的变量，一个指向前一个节点，一个指向后一个节点，对应下图prev指向前一个节点，next指向后一个节点。
这个概念也比较简单，就是链表首尾相连，造成一个环，比方单循环链表：
双向循环链表，第一个节点（头结点）的prev指向最初一个节点（尾节点），尾节点的next指向头结点：
咱们后面所提到的链表中的节点除了数据域（data）还有一个变量指向其余的节点，节点与节点之间的内存地址是不间断的，而动态链表和后面提到的链表不一样，它是应用数组来实现链表，只是将next变成一个int类型的数据，示意下一跳数据的下标，比方下图当中所示意的那样（其中-1示意链表的结尾，因为next域存储的是下一个节点的下标，下标必定大于等于0，因而能够应用-1示意链表的结尾）：
在上图当中对应的链表如下（通过剖析上图当中next域的指向剖析失去下图）：
像这种应用数组实现的链表叫做动态链表，下面谈到的就是动态单链表，它对应的数据结构也很分明：
private static class StaticNode {
// 指向节点的实在存储的数据
E item;
// 指向下一个节点的下标
int next;
public StaticNode(E item, int next) {
this.item = item;
this.next = next;
}
} 答复这个问题之前，首先须要搞清楚咱们面临什么样的需要：
在数组长度够的状况下，咱们须要将下标2之后的数据往后搬一个地位而后将新的数据放到下标为3的地位，这种插入的工夫复杂度为 O(n)，至于为什么是O(n)咱们在谈ArrayList时咱们再进行证实。
对于下面这种插入状况，咱们只须要略微扭转一下next的指向就能够了：
如果咱们须要在数组当中删除一个元素，同样的原理，因为某个数据被删除之后它所在的那个地位就空了，因而须要将后续的数据往前搬一个地位：
比方咱们须要删除下标为三的数据：
然而如果咱们应用的是链表的话咱们也只须要简略挪动链表即可，比方要删除节点N，只须要将节点N的上一个节点的next指向节点N的下一个节点即可，同时将节点N的next设置为空。
因为咱们在操作的时候只须要调整一下next指针的指向即可，这个操作的工夫复杂度是常数级别的，因而工夫复杂度为O(1)。
依据下面所谈到的内容，能够发现链表在这种须要频繁插入和删除的场景很适宜。
在正式实现双向链表之前咱们首先剖析一下咱们的需要：
咱们的需要次要就是下面这些了，当然也能够减少一些其余的办法，比如说减少将链表变成数组的办法等等，为了简略咱们只实现上述性能。
定义节点的数据结构
依据后面的剖析咱们很容易能够设计出链表当中节点的构造，其代码如下所示：
/**
* 本人实现链表
* @param 泛型，示意容器当中存储数据的数据类型
*/
public class MyLinkedList {
private static class Node {
// 指向节点的实在存储的数据
E item;
// 前向指针：指向前一个数据
Node prev;
// 后向指针：指向后一个数据
Node next;
public Node(E item, Node prev, Node next) {
this.item = item;
this.prev = prev;
this.next = next;
}
}
} 为了合乎设计模式，让咱们的代码更加清晰和容易保护，咱们能够设计一个接口（为了防止简单的接口信息咱们就用一个对立的接口示意）示意咱们要实现的性能，其代码如下：
public interface MyCollection {
/**
* 往链表尾部退出一个数据
* @param o 退出到链表当中的数据
* @return
*/
boolean add(E o);
/**
* 示意在第 index 地位插入数据 o
* @param index
* @param o
* @return
*/
boolean add(int index, E o);
/**
* 从链表当中删除数据 o
* @param o
* @return
*/
boolean remove(E o);
/**
* 从链表当中删除第 index 个数据
* @param index
* @return
*/
boolean remove(int index);
/**
* 往链表尾部退出一个数据，性能和 add 一样
* @param o
* @return
*/
boolean append(E o);
/**
* 返回链表当中数据的个数
* @return
*/
int size();
/**
* 示意链表是否为空
* @return
*/
boolean isEmpty();
/**
* 示意链表当中是否蕴含数据 o
* @param o
* @return
*/
boolean contain(E o);
} // 示意链表当中数据的个数
private int size;
// 链表当中第一个节点
private Node first;
// 示意链表当中最初一个节点
private Node last;
@Override
public boolean append(E o) {
final Node l = last;
// 新增的节点须要将 prev 指向上一个节点，上一个节点就是链表的 last 节点
// 新增节点的下一个节点就 null
final Node newNode = new Node<>(o, last, null);
last = newNode;
if (first == null) {
// 如果链表当中还没有节点，就将其作为第一个节点
first = newNode;
}else {
// 如果链表当中曾经有节点，须要将新增的节点连贯到链表的尾部
l.next = newNode;
}
size++;
return true;
} /**
* 依据下标找节点
* @param index
* @return
*/
Node findNodeByIndex(int index) {
if (index >= size)
throw new RuntimeException("输出 index 不非法链表中的数据个数为 " + size);
Node x;
// 首先看看 index 和 size / 2 的关系
// 这里次要是看链表的首和尾部谁间隔 index 地位近，那头近就从哪头遍历
// size >> 1 == size / 2
if (index <(size >> 1)) {
x = first;
for (int i = 0; i index; i--)
x = x.prev;
}
return x;
}
void removeNode(Node node) {
if (node == null)
throw new NullPointerException();
if (node.prev != null)
node.prev.next = node.next;
if (node.next != null)
node.next.prev = node.prev;
}
/**
* 依据下标删除某个节点
* @param index
* @return
*/
@Override
public boolean remove(int index) {
// 首先找到第 index 个数据对应的节点
Node node = findNodeByIndex(index);
// 删除节点
removeNode(node);
size--;
return true;
}
@Override
public String toString() {
if (first == null)
return "[]";
StringBuilder builder = new StringBuilder();
builder.append("[");
Node start = first;
builder.append(start.item.toString());
start = start.next;
while (start != null) {
builder.append(", ").append(start.item.toString());
start = start.next;
}
builder.append("]");
return builder.toString();
} public static void main(String[] args) {
MyLinkedList list = new MyLinkedList<>();
System.out.println(list.contain(100));
for (int i = 0; i <10; i++) {
list.add(i);
}
list.add(0, -9999);
System.out.println(list.size() / 2);
list.add(5, 9999);
list.append(Integer.MAX_VALUE);
System.out.println(list);
list.remove(5);
list.add(6, 6666);
System.out.println(list);
System.out.println(list.contain(6666));
} 输入
false
5
[-9999, 0, 1, 2, 3, 9999, 4, 5, 6, 7, 8, 9, 2147483647]
[-9999, 0, 1, 2, 3, 4, 6666, 5, 6, 7, 8, 9, 2147483647]
true双向链表实现残缺代码：
/**
* 本人实现链表
* @param 泛型，示意容器当中存储数据的数据类型
*/
public class MyLinkedList implements MyCollection {
// 示意链表当中数据的个数
private int size = 0;
// 链表当中第一个节点
private Node first;
// 示意链表当中最初一个节点
private Node last;
@Override
public boolean add(E o) {
return append(o);
}
@Override
public boolean add(int index, E o) {
Node node = findNodeByIndex(index);
insertBeforeNode(node, o);
size++;
return true;
}
/**
* 在节点数据 node 之后插入数据 o
* @param node
* @param o
*/
void insertAfterNode(Node node, E o) {
if (node == null)
throw new NullPointerException();
// newNode 后面的节点为 node 前面的节点是 node.next
Node newNode = new Node<>(o, node, node.next);
if (node.next != null)
node.next.prev = newNode;
if (node == last)
last = newNode;
node.next = newNode;
}
/**
* 在节点 node 之前插入数据 o
* @param node
* @param o
*/
void insertBeforeNode(Node node, E o) {
if (node == null)
throw new NullPointerException();
// newNode 后面你的节点为 node.prev 前面的节点为 node
Node newNode = new Node<>(o, node.prev, node);
if (node.prev != null)
node.prev.next = newNode;
else
first = newNode;
node.prev = newNode;
}
/**
* 依据下标找节点
* @param index
* @return
*/
Node findNodeByIndex(int index) {
if (index >= size)
throw new RuntimeException("输出 index 不非法链表中的数据个数为 " + size);
Node x;
// 首先看看 index 和 size / 2 的关系
// 这里次要是看链表的首和尾部谁间隔 index 地位近，那头近就从哪头遍历
// size >> 1 == size / 2
if (index <(size >> 1)) {
x = first;
for (int i = 0; i index; i--)
x = x.prev;
}
return x;
}
void removeNode(Node node) {
if (node == null)
throw new NullPointerException();
if (node.prev != null)
node.prev.next = node.next;
if (node.next != null)
node.next.prev = node.prev;
}
@Override
public boolean remove(E o) {
Node start = first;
while (start != null) {
if (start.item.equals(o))
removeNode(start);
start = start.next;
}
size--;
return true;
}
/**
* 依据下标删除某个节点
* @param index
* @return
*/
@Override
public boolean remove(int index) {
// 首先找到第 index 个数据对应的节点
Node node = findNodeByIndex(index);
// 删除节点
removeNode(node);
size--;
return true;
}
@Override
public boolean append(E o) {
final Node l = last;
// 新增的节点须要将 prev 指向上一个节点，上一个节点就是链表的 last 节点
// 新增节点的下一个节点就 null
final Node newNode = new Node<>(o, last, null);
last = newNode;
if (first == null) {
// 如果链表当中还没有节点，就将其作为第一个节点
first = newNode;
}else {
// 如果链表当中曾经有节点，须要将新增的节点连贯到链表的尾部
l.next = newNode;
}
size++;
return true;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contain(E o) {
Node start = first;
while (start != null) {
if (start.item.equals(o))
return true;
start = start.next;
}
return false;
}
private static class Node {
// 指向节点的实在存储的数据
E item;
// 前向指针：指向前一个数据
Node prev;
// 后向指针：指向后一个数据
Node next;
public Node(E item, Node prev, Node next) {
this.item = item;
this.prev = prev;
this.next = next;
}
}
@Override
public String toString() {
if (first == null)
return "[]";
StringBuilder builder = new StringBuilder();
builder.append("[");
Node start = first;
builder.append(start.item.toString());
start = start.next;
while (start != null) {
builder.append(", ").append(start.item.toString());
start = start.next;
}
builder.append("]");
return builder.toString();
}
public static void main(String[] args) {
MyLinkedList list = new MyLinkedList<>();
System.out.println(list.contain(100));
for (int i = 0; i <10; i++) {
list.add(i);
}
list.add(0, -9999);
System.out.println(list.size() / 2);
list.add(5, 9999);
list.append(Integer.MAX_VALUE);
System.out.println(list);
list.remove(5);
list.add(6, 6666);
System.out.println(list);
System.out.println(list.contain(6666));
}
} 关注公众号：一无是处的钻研僧，理解更多计算机常识
下期咱们仔细分析JDK外部LinkedList具体实现，我是LeHung，咱们下期再见！！！
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有