【数据结构与算法 | 基础篇】模拟LinkedList实现的双向循环链表

简介: 【数据结构与算法 | 基础篇】模拟LinkedList实现的双向循环链表

1. 前言

前文我们分别实现了不带哨兵的单链表,带哨兵节点的双向链表,接着我们实现带哨兵节点的双向循环链表.双向循环链表只需一个哨兵节点,该节点的prev指针和next指针都指向了自身哨兵节点.

2. 实现双向循环链表的代码

例 :

//模拟双向循环链表
public class CircleLinkedList implements Iterable<Integer>{
    private static class Node{
        Node prev;
        int value;
        Node next;
 
        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }
    private static Node head = new Node(null, 10086, null);
    //只有一个哨兵节点, 并且哨兵节点的两个指针域都指向本身
    public CircleLinkedList() {
        head.prev = head;
        head.next = head;
    }
 
    //头插法
    public void addHead(int value) {
        Node p = head.next;
        Node q = new Node(head, value, p);
        head.next = q;
        p.prev = q;
 
    }
    //从头开始遍历
    public void Traverse1Head() {
        Node p = head.next;
        while (p != head) {
            System.out.println("该处节点的数据域的值是" + p.value);
            p = p.next;
        }
    }
    //从尾开始遍历
    public void Traverse1Tail() {
        Node p;
        for (p = head.prev; p != head; p = p.prev) {
            System.out.println("该处节点的数据域的值是" + p.value);
        }
    }
    //获取指定位置的值
    public static int get(int index) {
        Node p = findIndex(index);
        //此时该方法返回的是哨兵节点
        if (p == head) {
            throw new RuntimeException("哨兵节点不可获取值");
        }
        return p.value;
    }
    //从哨兵节点开始找指定索引的节点的值
    private static Node findIndex(int index) {
        //我们假设哨兵节点的索引为-1
        int count = -1;
        Node p = head;
        if (index < -1) {
            throw new RuntimeException("index输入不合法");
        }
        while (count < index) {
            p = p.next;
            //当p == head, 说明遍历一圈都没找到, 即index过大
            if (p == head) {
                throw new RuntimeException("输入无效的index");
            }
            count++;
        }
        return p;
    }
    //尾插法
    public void addTail(int value) {
        Node p = head.prev;
        Node q = new Node(p, value, head);
        p.next = q;
        head.prev = q;
    }
    //向指定索引的位置添加节点
    public void Insert(int index, int value) {
        //找到要插入节点的前一个节点
        Node p = findIndex(index - 1);
        Node q = new Node(p, value, p.next);
        p.next.prev = q;
        p.next = q;
    }
    //对指定索引的节点进行删除操作
    public void remove(int index) {
        //找到要插入节点的前一个节点
        //当index==0时, p指向哨兵节点
        Node p = findIndex(index - 1);
        p.next.next.prev = p;
        p.next = p.next.next;
    }
    //实现了Iterable接口, 可foreach循环
 
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head.next;
            @Override
            public boolean hasNext() {
                return p != head;
            }
 
            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }
}
 

3. 单元测试

@Test
    public void test1() {
        CircleLinkedList c = new CircleLinkedList();
        c.addHead(12);
        c.addHead(23);
        c.addHead(34);
        c.addHead(45);
        c.addHead(56);
        c.addHead(67);
        c.addHead(78);
        c.Traverse1Head();
//        c.Traverse1Tail();
//        System.out.println(c.get(6));
    }
    @Test
    public void test2() {
        CircleLinkedList c = new CircleLinkedList();
        c.addTail(12);
        c.addTail(23);
        c.addTail(34);
        c.addTail(45);
        c.addTail(56);
        c.addTail(67);
        c.addTail(78);
        c.Insert(7, 100);
        c.remove(7);
        c.remove(0);
//        c.Traverse1Head();
        c.Traverse1Head();
    }
    @Test
    public void test3() {
        CircleLinkedList c = new CircleLinkedList();
        c.addTail(12);
        c.addTail(23);
        c.addTail(34);
        c.addTail(45);
        c.addTail(56);
        c.addTail(67);
        c.addTail(78);
        for (int element : c) {
            System.out.println("该节点的数据域是" + element);
        }
    }
相关文章
|
4天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
8天前
|
存储 缓存 算法
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
11 0
|
8天前
|
算法
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
17 0
|
8天前
|
算法
数据结构和算法学习记录——习题-移除链表元素
数据结构和算法学习记录——习题-移除链表元素
7 0
|
23小时前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
8天前
|
存储 算法
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
8 0
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
|
8天前
|
算法
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
9 0
|
8天前
|
算法
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
8 0
|
8天前
|
算法
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
7 0
|
8天前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
8 0