Data Structures (二) - 链表LinkedList实现(Part B)

简介: Data Structures (二) - 链表LinkedList实现(Part B)

一、双向链表DoubleLinkedList

单向链表的缺点是只能单向查询节点,即只能从头节点不断的调用next来获取洗一个节点,如果链表中节点元素非常多,会导致查询效率低下

image.png

可以从第一个节点开始调用next往后查询,也可以从尾节点不断调用prev从后往前查询,根据查询的index是在前半段还是后半段进行查询,相比单向链表,可以节省查询时间

修改Node节点实体类,增加prev属性

public class Node<T> {
    public T element;
    public Node<T> next;
    public Node<T> prev;
    // 此处省略有参构造/无参构造/getter/setter方法
}
复制代码

将linked包中原来的LinkedList复制一份重命名为SingleLinkedList即单向链表,将LinkeListWithDummyHead重命名为SingleLinkedListWithDummyHead,再将LinkedList复制一份重命名为DoubleLinkedList即双向链表,在单向链表的基础上进行双向链表的改造

首先单向链表中除了继承来的属性外还包含了一个头节点,双向链表需要增加一个尾节点的属性

// 第一个Node节点
private Node<T> first;
// 尾节点
private Node<T> last;
复制代码

第一个要修改的成员方法就是getNodeByIndex(int index)方法,单向链表中查找方式是根据头节点不断的调用getNext()或者next一个一个的查询节点,知道第index个节点,而双向链表可以先判断index是在链表的前半段还是后半段,从而选择从前往后查询还是从后往前查询

//获取指定索引对应的元素
public Node getNodeByIndex(int index){
    CheckUtils.checkIndex(index,size);
    Node<T> node = null;
    if (index < size >> 1){
        node = first;
        for (int i = 0; i < index; i++) {
            node = node.getNext();
        }
    } else {
        node = last;
        for (int i = size - 1; i > index; i--) {
            node = node.getPrev();
        }
    }
    return node;
}
复制代码

第二个要修改的方法是clear方法,需要将尾节点的指向也改为null

@Override
public void clear() {
    size = 0;
    first = null;
    last = null;
}
复制代码

第三个要修改的方法是add(int index, T element),为保证链表不断,现将新加入的节点的prev只想原来index位置节点的prev节点,新加入节点的next指向原index位置的节点

image.png

以新加入的节点为参照,下面这三句代码就完成了新节点的next指向原index位置的节点,新节点的prev指向原index-1位置的节点

Node<T> next = getNodeByIndex(index);
Node<T> prev = next.prev;
Node<T> node = new Node<>(element, prev, next);
复制代码

image.png

将原index-1位置节点的next指向新节点,将原来index位置的prev指向新节点

next.prev = node;
prev.next = node;
复制代码

如果添加到0位置,那么这个节点就是头节点

first=node
复制代码

如果添加到最后一个,那么这个节点就是尾节点

Node<T> oldLast = last;
last = new Node<T>(element, last, null);
oldLast.next = last;
复制代码

如果是空链表的情况下,新加入的节点就是第一个节点

fist = last;
复制代码

add(int index, T element)方法完整代码

@Override
public void add(int index, T element) {
    CheckUtils.checkIndex4Add(index,size);
    if (index == size){
        Node<T> oldLast = last;
        last = new Node<T>(element, last, null);
        if (oldLast == null){
            first = last;
        } else {
            oldLast.next = last;
        }
    } else {
        Node<T> next = getNodeByIndex(index);
        Node<T> prev = next.prev;
        Node<T> node = new Node<>(element, prev, next);
        if (prev == null) {
            first = node;
        } else {
            next.prev = node;
        }
        prev.next = node;
    }
    size++;
}
复制代码

第四个修改的方法就是remove方法,首先获取index位置的节点以及上一个节点prev以及下一个节点next,删除index位置节点只需要prev的下一个节点指向next,next的上一个节点指向prev,如果删除的是头节点,那么头节点就变为next节点(指定删除节点的下一个节点),如果删除的是尾节点,那么last节点就是prev节点(指定删除节点的上一个节点)

@Override
public T remove(int index) {
    CheckUtils.checkIndex(index,size);
    Node<T> node = getNodeByIndex(index);
    Node<T> prev = node.prev;
    Node<T> next = node.next;
    if (prev == null){
        first = next;
    } else {
        prev.next = next;
    }
    if (next == null){
        last = prev;
    } else {
        next.prev = prev;
    }
    size --;
    return node.element;
}
复制代码

新建一个DoubleLinkedTest测试类,增加测试方法

public class DoubleLinkedListTest {
    List<Integer> linkedList = new DoubleLinkedList<>();
    @Before
    public void init() {
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        System.out.println("初始化:" + linkedList);
    }
    @Test
    public void add() {
        linkedList.add(11);
        linkedList.add(34);
        linkedList.add(78);
        linkedList.add(1,99);
        System.out.println("执行add方法后," + linkedList);
    }
    @Test
    public void remove(){
        linkedList.remove(0);
        System.out.println("执行remove方法删除索引0位置的元素后," + linkedList);
        linkedList.remove(2);
        System.out.println("再次执行remove方法删除索引2位置的元素后," + linkedList);
    }
    @Test
    public void indexOf(){
        int i = linkedList.indexOf(3);
        System.out.println("执行indexOf,元素3位置的索引为:" + i);
    }
}
复制代码

执行所有方法的测试,控制台输出执行结果

image.png

二、单向循环链表

单向循环链表即单向链表的最有一个元素的next指向第一个元素

image.png

将linked包中的LinedList复制一份重命名为CircularLinkedList

首先修改add方法

@Override
public void add(int index, T element) {
    CheckUtils.checkIndex4Add(index,size);
    if (index == 0){
        first = new Node<T>(element,first);
        // 拿到最后一个节点,如果size=0就获取第一个节点
        Node<T> last = (size == 0) ? first : getNodeByIndex(size - 1);
        last.next = first;
    } else {
        Node<T> prev = getNodeByIndex(index - 1);
        prev.next = new Node<>(element,prev.next);
    }
    size++;
}
复制代码

第二个要修改的方法是remove方法

@Override
public T remove(int index) {
    CheckUtils.checkIndex(index,size);
    Node<T> node = first;
    if (index == 0){
        if (size == 1){
            first = null;
        } else {
            Node<T> last = getNodeByIndex(size - 1);
            first = first.next;
            last.next = first;
        }
    } else {
        Node<T> prev = getNodeByIndex(index - 1);
        node = prev.next;
        prev.next = node.next;
    }
    size --;
    return node.element;
}
复制代码

新建一个测试类,执行这两个方法的测试

public class CircularLinkedListTest {
    List<Integer> linkedList = new CircularLinkedList<>();
    @Before
    public void init() {
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        System.out.println("初始化:" + linkedList);
    }
    @Test
    public void add() {
        linkedList.add(11);
        linkedList.add(34);
        linkedList.add(78);
        linkedList.add(1,99);
        System.out.println("执行add方法后," + linkedList);
    }
    @Test
    public void remove(){
        linkedList.remove(0);
        System.out.println("执行remove方法删除索引0位置的元素后," + linkedList);
        linkedList.remove(2);
        System.out.println("再次执行remove方法删除索引2位置的元素后," + linkedList);
    }
}
复制代码

执行所有方法的测试,控制台输出如下

image.png

三、双向循环链表

复制DoubleLinekedList并重命名为DoubleCircularLinkedList,相比双向链表,双向循环链表需要对add方法和remove方法修改

add方法中往最后面添加元素的情况需要修改,双向循环链表往最后添加元素,这个元素的next需要指向first,往第一个位置添加元素的情况也需要修改

@Override
public void add(int index, T element) {
    CheckUtils.checkIndex4Add(index,size);
    if (index == size){
        Node<T> oldLast = last;
        // 最后一个位置插入元素
        last = new Node<T>(element, last, first);
        if (oldLast == null){
            first = last;
            // 只有一个元素的情况下,它的next和prev都指向自己
            first.next = first;
            first.prev = first;
        } else {
            oldLast.next = last;
            first.prev = last;
        }
    } else {
        Node<T> next = getNodeByIndex(index);
        Node<T> prev = next.prev;
        Node<T> node = new Node<>(element, prev, next);
        next.prev = node;
        prev.next = node;
        if (next == first) { // index == 0
            first = node;
        }
    }
    size++;
}
复制代码

针对remove方法进行修改

@Override
public T remove(int index) {
    CheckUtils.checkIndex(index,size);
    Node<T> node = first;
    if (size == 1){
        first = null;
        last = null;
    } else {
        node = getNodeByIndex(index);
        Node<T> prev = node.prev;
        Node<T> next = node.next;
        prev.next = next;
        prev.prev = prev;
        if (node == first) {
            first = next;
        }
        if (node == last){
            last = prev;
        }
    }
    size --;
    return node.element;
}
复制代码

增加测试类

public class DoubleCircularLinkedListTest {
    List<Integer> linkedList = new DoubleCircularLinkedList<>();
    @Before
    public void init() {
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        System.out.println("初始化:" + linkedList);
    }
    @Test
    public void add() {
        linkedList.add(11);
        linkedList.add(34);
        linkedList.add(78);
        linkedList.add(1,99);
        System.out.println("执行add方法后," + linkedList);
    }
    @Test
    public void remove(){
        linkedList.remove(0);
        System.out.println("执行remove方法删除索引0位置的元素后," + linkedList);
        linkedList.remove(2);
        System.out.println("再次执行remove方法删除索引2位置的元素后," + linkedList);
    }
}
复制代码

执行测试

image.png


相关文章
|
4月前
|
存储 Java
|
7月前
|
数据采集 Java 数据处理
Java流与链表:探索java.util.stream与LinkedList的交汇点
本文探讨了Java中流(Streams)与链表(LinkedList)的结合使用,展示了如何通过流处理LinkedList以实现高效数据操作。示例代码包括LinkedList的基本操作、使用Stream进行过滤和映射,以及结合HttpClient和代理IP实现网络爬虫。代理IP有助于绕过反爬机制,提高爬取效率。通过结合这些技术,开发者能编写出更简洁、高效的代码。
Java流与链表:探索java.util.stream与LinkedList的交汇点
|
7月前
|
算法 测试技术
【数据结构与算法 | 基础篇】模拟LinkedList实现的双向循环链表
【数据结构与算法 | 基础篇】模拟LinkedList实现的双向循环链表
|
7月前
|
存储 算法 Java
【数据结构与算法 | 基础篇】模拟LinkedList实现的双向链表
【数据结构与算法 | 基础篇】模拟LinkedList实现的双向链表
|
7月前
|
算法
【数据结构与算法 | 基础篇】模拟LinkedList实现的链表(无哨兵)
【数据结构与算法 | 基础篇】模拟LinkedList实现的链表(无哨兵)
|
7月前
|
存储 Python
链表(Linked List)详解
链表(Linked List)详解
51 0
|
7月前
|
设计模式 测试技术
在实现链表的代码中,为什么要使用`Node`类而不是直接在`LinkedList`类中定义节点?
在实现链表的代码中,为什么要使用`Node`类而不是直接在`LinkedList`类中定义节点?
62 1
|
7月前
|
存储 算法 Linux
【C/C++ 线性表】C++ 从零开始实现 双向循环链表(Exploring Doubly Circular Linked List in C++)
【C/C++ 线性表】C++ 从零开始实现 双向循环链表(Exploring Doubly Circular Linked List in C++)
125 0
|
7月前
|
算法 Java 索引
【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码)
【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码)
70 0
|
7月前
|
存储 算法 Java
【数据结构与算法】2、链表(简单模拟 Java 中的 LinkedList 集合,反转链表面试题)
【数据结构与算法】2、链表(简单模拟 Java 中的 LinkedList 集合,反转链表面试题)
68 0