IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 双向循环链表及其实现 -> 正文阅读

[数据结构与算法]双向循环链表及其实现

目录

1.什么是双向循环链表?

2.双向循环链表的具体实现方法有哪些?


1.什么是双向循环链表?

? ? ? ?双向循环链表结构是两个指针,一个头指针(指向链表的头部),一个尾指针(指向链表的尾部),当前循环链表的长度size. 每个节点LinkedNode由一个前向的指针,一个后向的指针,一个当前节点的值。

2.双向循环链表的具体实现方法有哪些?

? ? ? ? int get(int index)? 获得指定的元素

? ? ? ? int?addAtHead(int val) 头结点新增元素

? ? ? ? int?addAtTail(int val)尾节点新增元素

? ? ? ? int?addAtIndex(int index,int val) 指向索引的值

? ? ? ?void?deleteAtIndex(int index) 按照索引删除元素

? ? ? void printLinkedList()? 输出链表中的元素

代码如下

//双向循环链表
class MyLinkedList {
    int size;//当前链表的长度
    // sentinel nodes as pseudo-head and pseudo-tail
    ListNode head; //头结点
    ListNode tail; //尾节点

    //双向链表的初始化
    public MyLinkedList() {
        size = 0;
        head = new ListNode(-1);
        tail = new ListNode(-1);
        head.next = tail;
        tail.prev = head;
    }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        ListNode node = getNode(index);
        if (node == null) {
            return -1;
        }
        return node.val;
    }

    public ListNode getNode(int index) {
        // if index is invalid
        if (index < 0 || index >= size){
            return null;
        }

        // choose the fastest way: to move from the head
        // or to move from the tail
        ListNode curr = head;
        if (index < (size - 1) / 2) {
            //在左边从头结点进行寻找
            for (int i = 0; i < index + 1; ++i) {
                curr = curr.next;
            }
        } else {
            //在右边从尾节点进行寻找
            curr = tail;
            for (int i = 0; i < size - index; ++i) {
                curr = curr.prev;
            }
        }
        return curr;
    }

    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        ListNode pred = head, succ = head.next;

        ++size;
        ListNode newNode = new ListNode(val);
        newNode.prev = pred;
        newNode.next = succ;

        pred.next = newNode;
        succ.prev = newNode;
    }

    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        ListNode succ = tail, pred = tail.prev;

        ++size;
        ListNode newNode = new ListNode(val);
        newNode.prev = pred;
        newNode.next = succ;

        pred.next = newNode;
        succ.prev = newNode;
    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        // If index is greater than the length,
        // the node will not be inserted.
        if (index <0) {
            addAtHead(val);
            return;
        }
        if (index >(size - 1)) {
            addAtTail(val);
            return;
        }

        //找到前驱和后继
        // find predecessor and successor of the node to be added

        ListNode node = getNode(index);

        ListNode pred = node.prev;
        ListNode succ = node;
        // insertion itself
        ++size;
        ListNode toAdd = new ListNode(val);
        toAdd.prev = pred;
        toAdd.next = succ;
        pred.next = toAdd;
        succ.prev = toAdd;
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        // if the index is invalid, do nothing
        if (index < 0 || index >= size) {
            return;
        }

        // find predecessor and successor of the node to be deleted
        ListNode node = getNode(index);
        ListNode pred = node.prev;
        ListNode succ = node.next;
        // delete pred.next
        --size;
        pred.next = succ;
        succ.prev = pred;
    }

    public void printLinkedList() {
        for (int i = 0; i < size; i++) {
            System.out.println(get(i));
        }
    }

    class ListNode {
        int val;
        ListNode next;
        ListNode prev;

        ListNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
//        ["MyLinkedList","addAtIndex","addAtIndex","addAtIndex","get"]
//[[],[0,10],[0,20],[1,30],[0]]
//        MyLinkedList myLinkedList = new MyLinkedList();
//        myLinkedList.addAtTail(1);
//        myLinkedList.addAtTail(2);
//        myLinkedList.addAtTail(3);
//        myLinkedList.addAtHead(4);
//        System.out.println("====================");
//        myLinkedList.printLinkedList();
//        System.out.println("====================");
//        int num = myLinkedList.get(1);
//        System.out.println(num);
//        System.out.println("====================");
//        myLinkedList.addAtIndex(1,10);
//        myLinkedList.printLinkedList();

//        MyLinkedList myLinkedList = new MyLinkedList();
//        myLinkedList.addAtIndex(0,10);
//        myLinkedList.addAtIndex(0,20);
//        myLinkedList.addAtIndex(1,30);
//        System.out.println("===================");
//        myLinkedList.printLinkedList();
//        System.out.println("===================");
//        int num = myLinkedList.get(0);
//        System.out.println(num);

//        ["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get"]
//[[],[1],[3],[1,2],[1],[1],[1]]

        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addAtHead(1);
        myLinkedList.addAtTail(3);
        myLinkedList.addAtIndex(1,2);
        System.out.println("===================");
        myLinkedList.printLinkedList();
        System.out.println("===================");
        int num = myLinkedList.get(1);
        System.out.println(num);
        myLinkedList.deleteAtIndex(1);
        System.out.println("===================");
        int num2 = myLinkedList.get(1);
        System.out.println(num2);
    }
}

我是厚积薄发,欢迎大家点赞,欢迎大家留言。

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-09-26 10:26:26  更:2021-09-26 10:26:50 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 6:52:15-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码