我们知道线性表的链式存储结構的实现在Java中是以linkedlist实现来实现的。那么我们用了这么久的linkedlist实现如果不知道linkedlist实现的底层实现岂不是十分的滑稽，让我们来揭开它神秘的面紗

1）构建我们自己的List接口

我们可以尝试写出最基本的抽象方法。比如求集合中元素的个数方法等

 
 
 
 //定义节点静态内部类
 
 
 

 请大家仔细体会玳码的实现细节。
 
 

前几天看到了一篇文章,,感觉不错嘚..所以就整理的我的博客中,,方便以后查看..嘻嘻嘻~~开整~~

其实当面试问你 ArrayList、List、linkedlist实现 区别时面试官并不是仅仅想问你用法区别，而是想透过这個问题来了解你对日常工作中经常用到的东西有没有稍微深入的了解和深入程度从而看出你对技术的钻研程度和爱好。

List 是集合列表接口ArrayList 和 linkedlist实现 都是 List 接口的实现类。ArrayList 是动态数组顺序表顺序表的存储地址是连续的，所以查找比较快但是插入和删除时由于需要把其它的元素顺序移动，所以比较耗时linkedlist实现 是双向链表的数据结构，同时实现了双端队列 Deque 接口链表节点的存储地址是不连续的，每个存储地址通過指针关联在查找时需要进行指针遍历节点，所以查找比较慢而在插入和删除时比较快。

问：谈谈你理解的 linkedlist实现 工作原理和实现

答：linkedlist实现 是以双向链表实现，链表无容量限制（但是双向链表本身需要消耗额外的链表指针空间来操作）其内部主要成员为 first 和 last 两个 Node 节点，茬每次修改列表时用来指引当前双向链表的首尾部位所以 linkedlist实现 不仅仅实现了 List 接口，还实现了 Deque 双端队列接口（该接口是 Queue 队列的子接口）故 linkedlist实现 自动具备双端队列的特性，当我们使用下标方式调用列表的 get(index)、set(index, e) 方法时需要遍历链表将指针移动到位进行访问（会判断 index 是否大于链表長度的一半决定是首部遍历还是尾部遍历访问的复杂度为 O(N/2)），无法像 ArrayList 那样进行随机访问(如果i>数组大小的一半，会从末尾移起)只有在鏈表两头的操作（譬如 add()、addFirst()、removeLast() 或用在 iterator() 上的 remove() 操作）才不需要进行遍历寻找定位。具体感兴趣可以去看下 linkedlist实现 的源码

问：请使用 linkedlist实现 模拟一个堆栈或队列的数据结构？

首先堆栈是先进后出队列是先进先出，linkedlist实现 不但实现了 List 接口还实现了 Deque 双端队列接口接着给出实现如下。