Java数据结构-2 链表，模拟LinkedList实现

 链表是我们日常编程中使用频率最高的数据结构之一，它的定义为：

一种链式存储的线性表，用一组地址任意的存储单元存放线性表的数据元素，称存储单元为一个节点。

 链表也是线性表的一种，与同是线性表的顺序表比起来，却有很大的区别：

• 顺序表由数组实现，会有存储空间的限制。而链表由一个个存储节点组成，理论上不存在空间限制。
• 顺序表的元素的访问时间复杂度为O(1)，而链表节点的访问时间复杂度为O(n)。
• 顺序表删除插入节点时间复杂度为O(n)，而链表为O(1)。

 关于链表的具体解释，大家可以参考：

  链表及相关函数实现

 接下来，以Collection接口中的LinkedList类为模板，为大家介绍双链表的实现。

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList是集合类的一种，定义里的继承以及实现关系是集合类要掌握的知识，和我们今天主题不搭边，有兴趣了解集合类的同学可以参考:

Java 集合类

接下来，上代码。

package myLinkedList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MyLinkedList<T> implements Iterable<T> {
/**
* 内部属性
*/
// 链表长度
private int theSize;
// 链表修改次数，主要用于iterator对象中方法的使用
private int modCount = 0;
// 存储链表头节点，方便操作
private Node<T> head;
// 存储链表尾节点，同上
private Node<T> tail;
/**
* 由内部类来存储链表节点数据
*/
private static class Node<T> {
private T value;
private Node<T> pre;
private Node<T> next;
public Node(T value, Node<T> pre, Node<T> next) {
this.value = value;
this.pre = pre;
this.next = next;
}
}
// 无参构造
public MyLinkedList() {
// 调用构造方法时，初始化双链表
doClear();
}
/*********************** MyLinkedList 对外显示的方法 ***************************/
/**
* 清空双链表
*/
public void clear() {
doClear();
}
/**
* 返回双链表长度
* @return 双链表长度
*/
public int size() {
return this.theSize;
}
/**
* 双链表是否为空
* @return true双链表为空， false双链表不为空
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* 双链表尾插
* @param x 尾插元素的值
* @return 成功插入
*/
public boolean add(T x) {
add(size(), x);
return true;
}
/**
* 在指定下标处添加元素
* @param index 要插入节点的位置
* @param x 要插入节点的值
* @return 成功插入
*/
public boolean add(int index, T x) {
addBefore(getNode(index, 0, size()), x);
return true;
}
/**
* 取指定下标节点的值
* @param index 下标
* @return 节点的值
*/
public T get(int index) {
return getNode(index).value;
}
/**
* 设置指定下标的元素值，并返回旧的值
* @param index 要设置的节点的位置
* @param newValue 设置的值
* @return 返回旧的值
*/
public T set(int index, T newValue) {
Node<T> node = getNode(index);
T old = node.value;
node.value = newValue;
return old;
}
/**
* 删除指定下标的元素，并返回删除元素的值
* @param index 要删除的节点的位置
* @return 删除节点的值
*/
public T remove(int index) {
return remove(getNode(index));
}
/*********************** MyLinkedList 内部方法 ***************************/
/**
* 清空双链表
*/
private void doClear() {
this.head = new Node<>(null, null, null);
this.tail = new Node<>(null, head, null);
head.next = tail;
this.theSize = 0;
this.modCount++;
}
/**
* 在指定节点前插入值为x的元素
* @param node 位置
* @param x 插入节点的值
*/
private void addBefore(Node<T> node, T x) {
Node<T> newNode = new Node<>(x, node.pre, node);
newNode.pre.next = newNode;
newNode.next.pre = newNode;
this.theSize++;
this.modCount++;
}
/**
* 删除指定元素
* @param node 要删除的节点
* @return 删除节点的值
*/
private T remove(Node<T> node) {
node.pre.next = node.next;
node.next.pre = node.pre;
this.theSize++;
this.modCount++;
return node.value;
}
/**
* 根据指定下标得到对应的节点
* @param index 下标
* @return 指定下标的节点
*/
private Node<T> getNode(int index) {
return getNode(index, 0, size()-1);
}
/**
* 在指定范围内根据下标找到对应节点
* @param index 要查找的节点下标
* @param lower 范围下界
* @param upper 范围上界
* @return 对应下标的节点
*/
private Node<T> getNode(int index, int lower, int upper) {
Node<T> cur = null;
if(index<lower || index>upper) {
throw new IndexOutOfBoundsException();
}
// 根据index的大小，分别从头或尾出发，这对于链表的查找来说能够提高效率
if(index < size()/2) {
cur = this.head;
for(int i = 0; i < index; i++) {
cur = cur.next;
}
} else {
cur = this.tail;
for(int i = size(); i > index; i--) {
cur = cur.pre;
}
}
return cur;
}
/**
* 模拟实现LinkedList类的iterator方法
* @return Iterator的一个对象
*/
@Override
public Iterator<T> iterator() {
// 这里我们返回一个继承了 iterator 接口的嵌套类
return new LinkedListIterator();
}
/**
* 继承了Iterator接口的实现类
*/
private class LinkedListIterator implements Iterator<T> {
private Node<T> currentNode = head;
private int expectedModCount = modCount;
private boolean canRemove = false;
@Override
public boolean hasNext() {
return currentNode !=
tail;
}
@Override
public T next() {
if(modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if(!hasNext()) {
throw new NoSuchElementException();
}
T nextValue = currentNode.value;
currentNode = currentNode.next;
canRemove = true;
return nextValue;
}
@Override
public void remove() {
if(modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if(!canRemove) {
throw new IllegalStateException();
}
MyLinkedList.this.remove(currentNode.pre);
expectedModCount++;
canRemove = false;
}
}
}

 关于LinkedList模拟实现代码，我已上传至 我的GitHub，欢迎大家指导。

最后

以上就是粗心万宝路为你收集整理的Java数据结构-2 链表，模拟LinkedList实现的全部内容，希望文章能够帮你解决Java数据结构-2 链表，模拟LinkedList实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。