自己动手撸一个LinkedList
2024-09-01 12:14:49
自己动手撸一个LinkedList
1. 原理
LinkedList是基于双链表的动态数组，数据添加删除效率高，只需要改变指针指向即可，但是访问数据的平均效率低，需要对链表进行遍历。因此，LinkedList善于进行一些插入、删除操作，不利于进行检索操作。LinkedList和ArrayList这两个list在我们代码里会经常用到，因此，小编自定义实现LinkedList的简易版--MyLinkedList。
2. public API
void clear() --> 置空
boolean isEmpty() --> 判空
int size() --> 返回链表的长度
AnyType get(int idx) --> 根据索引检索元素
AnyType set(int idx) --> 根据索引跟新元素
boolean add(AnyType x) --> 添加元素x
boolean add(AnyType x，int idx) --> 根据索引添加元素x
AnyType remove(int idx) --> 根据索引删除元素x
String toString() --> 打印链表
3. 图解核心操作
一个节点Node类的数据结构
doClear( ) 方法，初始化一个双链表，先定义一个头结点beginMarker，然后定义一个尾结点endMarker，前驱指向头结点，最后头结点的后继指向尾结点。
添加元素，先定义一个被添加元素x的节点，使它前驱指向被插入位置的前一个，后继指向被插入位置的节点，这是第一步，然后将被插入的前一个节点的next指向此节点，被插入位置的节点的prev指向此节点。
Node<AnyType> newNode = new Node<>(x, p.prev, p); // ①②
newNode.prev.next = newNode; // ③
p.prev = newNode; // ④当然，第三步和第四步可以合并：
Node<AnyType> newNode = new Node<>(x, p.prev, p); // ①②
p.prev = p.prev.next = newNode; // ③④没想到以上4步全可以合并为：
p.prev = p.prev.next = new Node<>(x, p.prev, p); // ①②③④
精辟！
删除元素，根据索引找到对应的节点p，将p的后继的prev指向p的前驱，将p的前驱的next指向p的后继。
p.next.prev = p.prev;
p.prev.next = p.next;
检索节点getNode，LinkedList可以很快很方便地插入和删除元素，但是对于检索元素则就慢了，我们可以将索引分为前半部分和后半部分，如果索引在前半部分，我们就向后的方向遍历该链表；同样的道理，如果索引在后半部分，我们就从终端开始往回走，向前遍历该链表，这样可以提高一下检索速度吧。
// 从头结点开始向后找
if (idx < size() / 2) {
p = beginMarker.next;
for (int i = 0; i < idx; i++) {
p = p.next;
}
}
// 从尾节点开始向前找
else {
p = endMarker;
for (int i = size(); i > idx; i--) {
p = p.prev;
}
}
4. MyLinkedList代码实现
package com.hx.list; /**
* @author: wenhx
* @date: Created in 2019/10/17 16:11
* @description: 用双链表实现MyLinkedList
*/
public class MyLinkedList<AnyType> implements Iterable<AnyType> { private int theSize;
private int modCount = 0;
private Node<AnyType> beginMarker;
private Node<AnyType> endMarker; /**
* 内部类，定义链表的节点
*/
private static class Node<AnyType> { public AnyType data;
public Node<AnyType> prev;
public Node<AnyType> next; public Node(AnyType d, Node<AnyType> p, Node<AnyType> n) {
data = d;
prev = p;
next = n;
}
} /**
* 构造器
*/
public MyLinkedList() {
doClear();
} /**
* 判空
*/
public boolean isEmpty() {
return size() == 0;
} /**
* 清空
*/
public void clear() {
doClear();
} /**
* 返回链表的长度
*/
public int size() {
return theSize;
} /**
* 根据索引检索元素
*/
public AnyType get(int idx) {
return getNode(idx).data;
} /**
* 根据索引跟新元素
*/
public AnyType set(int idx, AnyType newVal) {
Node<AnyType> p = getNode(idx);
AnyType oldVal = p.data;
p.data = newVal;
return oldVal;
} /**
* 添加元素x
*/
public boolean add(AnyType x) {
add(size(), x);
return true;
} /**
* 根据索引添加元素
*/
public void add(int idx, AnyType x) {
addBefore(getNode(idx, 0, size()), x);
} /**
* 根据索引删除元素
*/
public AnyType remove(int idx) {
return remove(getNode(idx));
} /**
* 打印链表
*/
public String toString() {
StringBuilder sb = new StringBuilder("[ "); for (AnyType x : this) {
sb.append(x + " ");
}
sb.append("]"); return new String(sb);
} /**
* 清空链表（实现）
*/
private void doClear() {
beginMarker = new Node<>(null, null, null);
endMarker = new Node<>(null, beginMarker, null);
beginMarker.next = endMarker;
theSize = 0;
modCount++;
} /**
* 根据索引检索节点
*/
private Node<AnyType> getNode(int idx) {
return getNode(idx, 0, size() - 1);
} /**
* 检索节点
*/
private Node<AnyType> getNode(int idx, int lower, int upper) {
Node<AnyType> p; if (idx < lower || idx > upper) {
throw new IndexOutOfBoundsException("getNode index: " + idx + "; size: " + size());
} if (idx < size() / 2) {
p = beginMarker.next;
for (int i = 0; i < idx; i++) {
p = p.next;
}
} else {
p = endMarker;
for (int i = size(); i > idx; i--) {
p = p.prev;
}
} return p;
} /**
* 插入节点
*/
private void addBefore(Node<AnyType> p, AnyType x) {
Node<AnyType> newNode = new Node<>(x, p.prev, p);
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
modCount++;
} /**
* 删除节点p
*/
private AnyType remove(Node<AnyType> p) {
p.next.prev = p.prev;
p.prev.next = p.next;
theSize--;
modCount++; return p.data;
} /**
* 返回一个迭代器对象，用于遍历链表
*/
public java.util.Iterator<AnyType> iterator() {
return new LinkedListIterator();
} /**
* LinkedListIterator迭代器的实现
*/
private class LinkedListIterator implements java.util.Iterator<AnyType> { private Node<AnyType> current = beginMarker.next;
private int expectedModCount = modCount;
private boolean okToRemove = false; public boolean hasNext() {
return current != endMarker;
} public AnyType next() {
if (modCount != expectedModCount) {
throw new java.util.ConcurrentModificationException();
}
if (!hasNext()) {
throw new java.util.NoSuchElementException();
} AnyType nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
} public void remove() {
if (modCount != expectedModCount) {
throw new java.util.ConcurrentModificationException();
}
if (!okToRemove) {
throw new IllegalStateException();
} MyLinkedList.this.remove(current.prev);
expectedModCount++;
okToRemove = false;
}
} /**
* 主方法：用来测试MyLinkedList
*/
public static void main(String[] args) {
MyLinkedList<Integer> myLinkedList = new MyLinkedList<>(); for (int i = 0; i < 10; i++) {
myLinkedList.add(i);
}
for (int i = 20; i < 30; i++) {
myLinkedList.add(0, i);
} System.out.println(myLinkedList.toString());
System.out.println("----------");
myLinkedList.remove(0);
myLinkedList.remove(myLinkedList.size() - 1);
System.out.println(myLinkedList);
System.out.println("----------");
java.util.Iterator<Integer> itr = myLinkedList.iterator();
while (itr.hasNext()) {
itr.next();
itr.remove();
System.out.println(myLinkedList);
}
}
}
完成，撒花，一个迷你版的LinkedList就写好啦，下次有空再写一个迷你版的ArrayList...
后记：
若有不当之处，可向小编反馈，一起交流学习，共同进步。
个人博客地址：https://www.cnblogs.com/q964024886/
GitHub地址：https://github.com/wenhaixiong
最新文章
- 关于Java中的transient关键字
- 【阿里李战】解剖JavaScript中的 null 和 undefined
- MFC 单文档消息执行顺序。
- python装饰器初探
- Hadoop I/O操作原理整理
- sublimeLinter-jshint 配置
- 二叉树-你必须要懂！（二叉树相关算法实现-iOS）
- C++顺序容器类总结
- spring技术翻译开始
- 【拆点费用流】【HDU1853】【 Cyclic Tour】
- Web前端的路该怎么走？很迷茫
- python----数据驱动@ddt.file_data结合yaml文件的使用
- py2neo的使用（转）
- Css3实现波浪线效果1
- 【读书笔记】iOS-设计模式
- html5 required属性的注意事项
- [ Windows BAT Script ] 删除某个目录下的所有某类文件
- 百度“搜索设置”之基于定位下拉框或者需要点击link才显示的下拉框,二次定位与多次定位实现的实际效果区别
- Java Jackson - Json Polymorphism
- gulp的使用 文档