数据结构基础-链表

什么是链表

链表是用来存储数据集合的数据结构。有如下属性:

  • 相邻元素通过指针连接
  • 最后一个的后继指针为NULL
  • 链表长度可以增加和缩小
  • 空间按需分配,直至内存耗尽,但是存储指针会相对数组耗费一些额外空间

linkedlist

链表抽象数据结构

主要操作:

  • 添加元素,
  • 删除元素(移除并返回链表中指定位置的元素)

辅助操作:

  • 获取元素个数
  • 查询(寻找从链表表头开始的第n个结点),
  • 清空元素

这里给出插入和删除的java代码示例:

/* time:O(n) space:O(1) */
public ListNode insertLinkedList(ListNode headNode, ListNode nodeToInsert, int positon){
        if (headNode == null) {
            return nodeToInsert;
        }
        if (nodeToInsert == null) {
            return headNode;
        }
        //这里需要效验position是否在有效范围
        if (position == 0) {
            nodeToInsert.setNext(headNode);
            return nodeToInsert;
        }else {
            ListNode previousNode = headNode;
            for (int i = 1; i < positon; i++) {
                previousNode = previousNode.getNext();
            }
            nodeToInsert.setNext(previousNode.getNext());
            previousNode.setNext(nodeToInsert);
        }
        return headNode;
    }
    
public ListNode deleteNodeFromLinkedList(ListNode headNode, int position){
        if (position == 1) {
            ListNode currentNode = headNode.getNext();
            headNode = null;
            return currentNode;
        }else {
            ListNode previousNode = headNode;
            for (int i = 1; i < position; i++) {
                previousNode = previousNode.getNext();
            }
            ListNode curNode = previousNode.getNext();
            previousNode.setNext(curNode.getNext());
        }
        return headNode;
    }

为什么用链表

数组一样能用来存储数据集合,那为什么用多种数据结构来做一样的事情。因为后来发现数组在处理一些情况下的弊端,所以开始分使用情景用不同的工具干同样的事情。 先说说数组在一些情况下的缺点,

  • 大小是固定的,需要分配一块连续的空间块,就造成有时候无法分配能存储整个数组的内存空间(当数组规模太大时),(当然动态数组通过到达数组最大长度后再申请更大容量数组来加入新元素)大空间没有足量的元素也会造成空间的浪费。
  • 基于位置的插入操作实现复杂,考虑最糟的一种情况,插入到数组开始的位置,就需要移动原有数组的每一个元素。

对数组,链表最大的有点在于在任何位置插入元素的时间开销仅为O(1)。然而查找某个元素的开销为O(n)。

链表、数组和动态数组的对比

linedlist_compare

双向链表与循环链表

双向链表是单项链表的拓展,就是加入指向前一个结点的指针,用NULL表示指针的结束。循环指针就是头指针指向尾结点地址,形成了一个贪吃蛇的形状,没有NULL指针,需要注意无限循环遍历,因为每一个结点都有后继结点。

eg: 用链表实现栈

public class ListNodeStack{
    private ListNode headNode;
    public ListNodeStack(){
        this.headNode = new ListNode(null);
    }
    public void push(int data){
        if(headNode == null){
            headNode = new ListNode(data);
        }else if(headNode.getData() == null){
            headNode.setData(data);
        }else {
            ListNode node = new ListNode(data);
            node.setNext(headNode);
            headNode = node;
        }
    }
    public void pop(){
        if(isEmpty()){
            throw new EmptyStackException("Stack empty");
        }else {
            int data = headNode.getData();
            headNode = headNode.getNext();
            return data;
        }
    }
    public boolean isEmpty(){
        return null == headNode;
    }
    public void deleteStack(){
        headNode = null;
    }
}

eg1:知道链表倒数第n个结点

/* space:O(1) , time:O(n)*/
    public ListNode nthNodeFromEnd(ListNode head, int nthNode){
        ListNode fast = head, slow = head;
        for (int i = 1; i < nthNode; i++) {
            if (fast != null) {
                fast = fast.getNext();
            }
        }
        while(fast != null) {
            fast = fast.getNext();
            slow = slow.getNext();
        }
        return slow;
    }

eg2: 判定给定的链表是以NULL结尾,还是形成了一个环。 解决方法是经典的快慢指针法也叫Floyd环判定算法:试想一下乌龟和兔子在同一个轨道上赛跑。如果它们在同一个环上赛跑,那么跑得快的兔子将赶上跑得慢的乌龟,并在某一点相遇。

image

image

public boolean doesLinkedListContainerLoop(ListNode head){
        if (head == null) {
            return false;
        }
        LsitNode fastPtr = head, slowPtr = head;
        while (fastPtr != null && fastPtr.getNext() != ll) {
            fastPtr = fastPtr.getNext().getNext();
            slowPtr = slowPtr.getNext();
            if (fastPtr == slowPtr) {
                return true;
            }
        }
        return false;
    }

引申问题探究: 在前面的问题的求解方法中,一旦乌龟和兔子相遇就代表着链表中含有环。然后,乌龟从表头开始移动,而兔子从相遇的位置开始移动,乌龟和兔子每次都移动一个节点,当乌龟和兔子再次相遇,他们一定相遇在环的起始结点。WHY? 室友的帮助我理解加了下,下面是解答:题目基础是这个两个都从起点出发,在环中某个结点相遇。所以,假设环的结点个数或者长度为L,而链表头结点到环的结点的距离为m;假设第一次相遇距离环的起点为k;开始的环境是兔子每移动两步,乌龟移动一步,则从起点开始,兔子和乌龟开始出发,那么第一次相遇的时候,由于时间相同,乌龟移动S,兔子移动2S。而S = m + A * L + k (A为自然数);对应的2S = m + B * L + k (B为自然数);两者相减可得:S = (B - A) * L,由此可得两者相遇各自走过的路是相遇的整数倍。 现在兔子在第一次相遇的k处,也就是2S(S = C * L L为自然数),乌龟在链表的起点,兔子走一步乌龟也走一步,所以走m步是2S+m也就是环的起点,乌龟走m步就也是环的起点,so。

eg3:逆置单向列表

public ListNode reverseListUsingRecursion(ListNode head){
        if (head == null || head.getNext() == null) {
            return head;
        }
        ListNode newHead = reverseListUsingRecursion(head.getNext());
        head.getNext().setNext(head);
        head.setNext(null);
        return newHead;
    }

迭代版本

public ListNode reverseList(ListNode head){
        ListNode tmp = null, nextNode = null;
        while (head != null){
            nextNode = head.getNext();
            head.setNext(tmp);
            tmp = head;
            head = nextNode;
        }
        return tmp;
    }

eg4: 逆置链表,两个为单位进行逆置,eg:1->2->3->4->x => 2->1->4->3->x

//space:o(n), time:O(n)
public ListNode reversePairRecursive(ListNode head) {
        ListNode temp;
        if (head == null || head.getNext() == null) {
            return head;
        }
        temp = head.getNext();
        head.setNext(temp.getNext());
        temp.setNext(head);
        head = temp;
        head.getNext().setNext(reversePairRecursive(head.getNext().getNext()));
        return head;
    }

迭代版本代码:

/* space:o(1), time:O(n) */
    public ListNode reversePairIterative(ListNode head) {
        ListNode temp1 = null;
        ListNode temp2 = null;
        while (head != null && head.getNext() != null) {
            if (temp1 != null) {
                temp1.next().setNext(head.getNext());
            }
            temp1 = head.getNext();
            head.setNext(temp1.getNext());
            temp1.setNext(head);
            if (temp2 == null) {
                temp2 = temp1;
            }
            head = head.getNext();
        }
        return temp2;
    }

eg5: 逆置链表,k个为单位进行逆置,eg:1 2 3 4 5 6 7 8 9 10 , k=3: 3 2 1 6 5 4 9 8 7 10

public ListNode getKPlusOneThNode(int k, ListNode head) {
        ListNode kNode = head;
        if (head == null) {
            return head;
        }
        for (int i = 1; kNode != null && (i <= k); i++, kNode = kNode.getNext()) {
            if (k == i) {
                return kNode;
            }
        }
        return head.getNext();
    }

public boolean hasKNode(ListNode head, int k) {
        if (head == null) {
            return head;
        }
        for (int i = 1; head != null && (i <= k); i++, head = head.getNext()) {
            if (i == k) {
                return true;
            }
        }
        return false;
    }

public ListNode reverseBolckOf(ListNode head, int k) {
        ListNode newHead, curNode, temp, next;
        curNode = head;
        if (k ==0 || k == 1) {
            return head;
        }
        if (hasKNode(head, k)) {
            newHead = getKPlusOneThNode(k, head);
        }else {
            newHead = head;
        }
        while (curNode != null && hasKNode(curNode, k)) {
            temp = getKPlusOneThNode(k, curNode);
            int i = 0;
            while (i < k) {
                next = curNode.getNext();
                curNode.setNext(temp);
                temp = curNode;
                curNode = next;
                i++;
            }
        }
        return newHead;
    }

看动画理解「链表」实现LRU缓存淘汰算法

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏刨根究底学编程

刨根究底字符编码之十二——UTF-8究竟是怎么编码的

UTF-8编码是Unicode字符集的一种编码方式(CEF),其特点是使用变长字节数(即变长码元序列、变宽码元序列)来编码。一般是1到4个字节,当然,也可以更长...

14440
来自专栏刨根究底学编程

刨根究底字符编码之十四——UTF-16究竟是怎么编码的

首先要注意的是,代理Surrogate是专属于UTF-16编码方式的一种机制,UTF-8和UTF-32是不用代理的。

13430
来自专栏算法工程师的养成之路

牛顿法与拟牛顿法

牛顿法和拟牛顿法是求解无约束最优化的常用方法,有收敛速度快的优点. 牛顿法属于迭代算法,每一步需要求解目标函数的海赛矩阵的逆矩阵,计算复杂. 拟牛顿法通过正定...

24720
来自专栏指点的专栏

2018 团队设计天梯赛题解---华山论剑组

2018 年度的团队设计天梯赛前几天结束了。但是成绩真的是惨不忍睹。。。毕竟是团队的比赛,如果团队平均水平不高的话,单凭一个人,分再高也很难拉起来(当然,一个人...

88020
来自专栏老欧说安卓

Android开发笔记(十八)书籍翻页动画PageAnimation

前面几节的动画都算简单,本文就介绍一个复杂点的动画——书籍翻页动画。Android有自带的翻页动画ViewPager,不过V...

42540
来自专栏算法工程师的养成之路

数据降维(四)ISOMAP

Isomap(Isometric Feature Mapping)是流行学习的一种,用于非线性数据降维,是一种无监督算法.

13010
来自专栏老欧说安卓

Android开发笔记(二十七)对象序列化

程序中存储和传递信息,需要有个合适的数据结构,最简单的是定义几个变量,变量多了之后再分门别类,便成了聚合若干变量的对象。代码在函数调用时可以直接传递对象,但...

10740
来自专栏刨根究底学编程

刨根究底字符编码之十三——UTF-16编码方式

UTF-16编码方式源于UCS-2(Universal Character Set coded in 2 octets、2-byte Universal Cha...

13040
来自专栏中科院渣渣博肆僧一枚

tf.expand_dims()使用

他所实现的功能是给定一个input,在axis轴处给input增加一个为1的维度。 

1K30
来自专栏刨根究底学编程

刨根究底字符编码之零——前言

字符编码是计算机世界里最基础、最重要的一个主题之一。不过,在计算机教材中却往往浮光掠影般地草草带过,甚至连一本专门进行深入介绍的著作都找不到(对这一点我一直很困...

10620

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励