LinkedList中的链表结构

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来观察运行情况
  
  
  其中第5次曹操8内的node和曹操0连在了一起
  这个就是我们自己模拟了一个简单的链表结构,而且原理类似…