image redis常用语句 upload ionic3 progressjs vue实例 vue自定义事件 oracle数据库版本 本地安装mysql vue与html5 mysql插入 python中pop函数 python加入环境变量 python传递参数 java环境搭建 java8的新特性 java正则表达式匹配 java中数据类型 php案例 php整站源码 莫莫小工具 球中的小鬼 内存整理工具 亚索刀光特效包 volist 苹果滚动截屏 飞猪ip eml文件阅读器下载 linux运维之道 五子棋大师 proxies 铁血统帅 ssh框架原理及流程 服务器系统安装教程 情头污系 pygame安装教程 超级好友 keil5注册机下载 android模拟器下载 批处理
当前位置: 首页 > 学习教程  > 编程语言

LinkedList中的链表结构

2020/9/19 15:27:22 文章标签:

LinkedList

****类似链表结构,查询慢,增删快,线程不安全。**

双链表实现了List和Deque接口。 实现所有可选列表操作,并允许所有元素(包括null )。
所有的操作都能像双向列表一样预期。 索引到列表中的操作将从开始或结束遍历列表,以更接近指定的索引为准。

请注意,此实现不同步。 如果多个线程同时访问链接列表,并且至少有一个线程在结构上修改列表,则必须在外部进行同步。 (结构修改是添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。)这通常通过在自然封装列表的对象上进行同步来实现。 如果没有这样的对象存在,列表应该使用Collections.synchronizedList方法“包装”。 这最好在创建时完成,以防止意外的不同步访问列表:

List list = Collections.synchronizedList(new LinkedList(…)); 这个类的iterator和listIterator方法返回的迭代器是故障快速的 :如果列表在迭代器创建之后的任何时间被结构化地修改,除了通过迭代器自己的remove或add方法之外,迭代器将会抛出一个ConcurrentModificationException 。 因此,面对并发修改,迭代器将快速而干净地失败,而不是在未来未确定的时间冒着任意的非确定性行为。

请注意,迭代器的故障快速行为无法保证,因为一般来说,在不同步并发修改的情况下,无法做出任何硬性保证。 失败快速迭代器尽力投入ConcurrentModificationException 。 因此,编写依赖于此异常的程序的正确性将是错误的:迭代器的故障快速行为应仅用于检测错误。

其中结构为链表结构我们可以通过代码模拟一个普通的链表结构

1、什么是链表?

链表结构示意图

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针连接次序实现的。
每一个链表都包含多个节点,节点又包含两个部分,一个是数据域(储存节点含有的信息),一个是引用域(储存下一个节点或者上一个节点的地址)。

2、链表的特点是什么?

获取数据麻烦,需要遍历查找,比数组慢
方便插入、删除

3、链表的实现原理

创建一个节点类,其中节点类包含两个部分,第一个是数据域(你到时候要往节点里面储存的信息),第二个是引用域(相当于指针,单向链表有一个指针,指向下一个节点;双向链表有两个指针,分别指向下一个和上一个节点)
创建一个链表类,其中链表类包含三个属性:头结点、尾节点和大小,方法包含添加、删除、插入等等方法。

  • 需要创建一个自定义的方法类来实现node链表结构
package com.java01;

/**
 * 自定义集合 不使用Hash  使用的 hash值/8 余数
 */
public class MyHashMap {

    /**
     * 数据存放容器
     */
    private Node[] nodes;

    private int nodesSize;

    /**
     * 初始化集合大小
     */
    private final int DEFAULT_INITIAL_CAPACITY = 8;

    /**
     * 无参构造方法-初始化集合
     */
    public MyHashMap() {
        nodes = new Node[DEFAULT_INITIAL_CAPACITY];  // 初始化
    }

    /**
     * 根据Key 获取集合中数据
     */
    public Object get(Object key) {
        // 获取 key 余数值
        int tmp = key.hashCode() % DEFAULT_INITIAL_CAPACITY;

        // 递归算法
        Object value = getValue(key, nodes[tmp]);
        return value;
    }

    private Object getValue(Object key, Node node) {
        if (node.key.equals(key)) {
            return node.value;
        }
        if (node.node != null) {
            return getValue(key, node.node);
        } else {
            return null;
        }

    }

    /**
     * 获取集合长度
     *
     * @return
     */
    public int size() {
        return nodesSize;
    }

    /**
     * 添加数据到集合中
     *
     * @param key
     * @param value
     */
    public void put(Object key, Object value) {
        // 获取余数值
        int hash = key.hashCode();
        int index = hash % DEFAULT_INITIAL_CAPACITY;

        Node node = new Node(key, value, nodes[index]);
        nodes[index] = node;

        nodesSize++; // 设置集合长度+1
    }

    /**
     * 内部类 链表
     */
    private class Node {

        private Object key;

        private Object value;

        private Node node;

        public Node(Object key, Object value, Node node) {
            this.key = key;
            this.value = value;
            this.node = node;
        }
    }

}

  • 通过已经创建的 方法类,来实现自定义的链表结构]
package com.java01;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 自定义一个 Map集合
 */
public class Test {
    public static void main(String[] args) {

        MyHashMap myHashMap = new MyHashMap();

        for (int i = 0; i < 10; i++) {
            myHashMap.put("曹操" + i, "曹操" + i);
        }
        System.out.println(myHashMap.size());


        Object daat2 = myHashMap.get("曹操0");
        System.out.println(daat2);


    }
}

  • 通过debugger来观察运行情况
    循环遍历了10次
    在这里插入图片描述
    其中第5次曹操8内的node和曹操0连在了一起
    这个就是我们自己模拟了一个简单的链表结构,而且原理类似…

本文链接: http://www.dtmao.cc/news_show_200245.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?