开发者社区> 賢、> 正文

Java进阶-我的算法学习之路——《我的Java打怪日记》

简介: 最简单的数据结构--链表
+关注继续查看

链表

  1. 基础数据类型 背包、队列、栈

    1. 背包:是一种不支持从中删除元素的集合数据类型,它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素(用例也可以检查是否为空或者获取背包中元素的数量)。迭代的顺序不确定且与用例无关;
    2. 队列:队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

在队列这种数据结构中,最先插入的元素将是最先被删除的元素;反之最后插入的元素将最后被删除的元素,因此队列又称为“先进先出”(FIFO—first in first out)的线性表。;

  1. 栈:主要作用表现为一种数据结构,是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
  1. 链表

    1. 定义:是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

  1. 下压堆栈代码实现

    public class StackDemo<Item> implements Iterable<Item> {
        private int N;
        private Node first;
        private class Node {
            Item item;
            Node next;
        }
        /**
         * 链表是否为空
         *
         * @return
         */
        public boolean isEmpty() {
            return N == 0;
        }
        /**
         * 链表大小
         * @return
         */
        public int size() {
            return N;
        }
        /**
         * 添加
         * @param item
         */
        public void push(Item item) {
            Node old = first;
            first = new Node();
            first.item = item;
            first.next = old;
            N++;
        }
        /**
         * 删除最上面的节点
         * @return
         */
        public Item pop() {
            Item t = first.item;
            first = first.next;
            N--;
            return t;
        }
        @Override
        public Iterator<Item> iterator() {
            return new StackDemoIterator();
        }
        private class StackDemoIterator implements Iterator<Item> {
            private Node current = first;
            @Override
            public boolean hasNext() {
                return current != null;
            }
            @Override
            public Item next() {
                Item t = current.item;
                current = current.next;
                return t;
            }
        }
    }

  2. 队列实现

    public class QueueDemo<Item> implements Iterable<Item> {
        private Node first;
        private Node last;
        private int N;
        private class Node {
            Item item;
            Node next;
        }
        /**
         * 队列事否为空
         * @return
         */
        public boolean isEntity() {
            return first == null;
        }
        /**
         * 队列的大小
         * @return
         */
        public int size() {
            return N;
        }
         /**
           * 向队列中添加元数
           * @param item
           */
          public void enqueue(Item item) {
              Node oldLast = last;
              last = new Node();
              last.item = item;
              last.next = null;
              if (isEntity()) first = last;
              else oldLast.next = last;
              N++;
          }
    
          /**
           * 取出最先进入队列的元数,并从队列中删除
           * @return
           */
          public Item dequeue() {
              Item item = first.item;
              first = first.next;
              if (isEntity()) last = null;
              N--;
              return item;
          }
    
          @Override
          public Iterator<Item> iterator() {
              return new QueueDemoIterator();
          }
          private class QueueDemoIterator implements Iterator<Item> {
              private Node current = first;
              @Override
              public boolean hasNext() {
                  return current != null;
              }
              @Override
              public Item next() {
                  Item item = current.item;
                  current = current.next;
                  return item;
              }
          }
      }
  3. 背包实现

    ​ 背包的实现同栈的一样,仅是把pop()实现既可,push()改为add()

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
[解题报告]《算法零基础100讲》(第45讲) 位运算 (位或) 进阶
[解题报告]《算法零基础100讲》(第45讲) 位运算 (位或) 进阶
7 0
怎么设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程
10153 0
如何优化大规模推荐?下一代算法技术JTM来了 | 开发者必读(077期)
最炫的技术新知、最热门的大咖公开课、最有趣的开发者活动、最实用的工具干货,就在《开发者必读》!
423 0
Java进阶之并发编程——《我的Java打怪日记》
Java进阶之并发编程——《我的Java打怪日记》
37092 0
DL之NN/CNN:NN算法进阶优化(本地数据集50000张训练集图片),六种不同优化算法实现手写数字图片识别逐步提高99.6%准确率
DL之NN/CNN:NN算法进阶优化(本地数据集50000张训练集图片),六种不同优化算法实现手写数字图片识别逐步提高99.6%准确率
55 0
【阿里Java技术进阶】官方钉群直播大全(持续更新)
由于我们【阿里Java技术进阶】官方钉群中有粉丝私信小编,去年的直播课怎么在群中看不了了(ps:钉群可保存3个月内的直播回放),因此小编特别搜集了从2018年钉群成立到现在的所有直播内容,快快收藏起来,之后本文会持续更新哦~
542655 0
Java进阶-LinkedHashMap 底层分析
众所周知 HashMap 是一个无序的 Map,因为每次根据 key 的 hashcode 映射到 Entry数组上,所以遍历出来的顺序并不是写入的顺序。
965 0
Java进阶笔记——synchronized 关键字原理
众所周知 synchronized 关键字是解决并发问题常用解决方案,有以下三种使用方式: 同步普通方法,锁的是当前对象。
809 0
DL之NN:NN算法(本地数据集50000张训练集图片)进阶优化之三种参数改进,进一步提高手写数字图片识别的准确率
上一篇文章,比较了三种算法实现对手写数字识别,其中,SVM和神经网络算法表现非常好准确率都在90%以上,本文章进一步探讨对神经网络算法优化,进一步提高准确率,通过测试发现,准确率提高了很多。
29 0
+关注
1
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载