首页 > 代码库 > JAVA容器-模拟LinkedList实现(双链表)
JAVA容器-模拟LinkedList实现(双链表)
一、概述
LinkedList实质上就是双向链表的拓展的实现，我们将关注一下问题。LinkedList
1、双向链表怎么来实现插入、删除、查询？
2、利用二分法提高查询效率。
3、不同步，线程不安全，需要使用Collections.synchronizedList()达到线程安全。
4、简单说，LinkedList就是数据结构中关于数据操作吗？
二、模拟实现
1、实现总体图(初始状态)
2、论述双链表的实现思想
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。查询即从第一个节点，不断指向下一节点以便获得自己目标节点。删除、插入同理，最后修改目标节点的前后关系即可，就不多论述了。
3、采用二分法，向下遍历节点
1 public Node node(int index){ 2 Node temp=first; 3 //采用二分法遍历节点 4 if(index<size<<1){ 5 for(int i=0;i<index;i++){ 6 temp=temp.getNext(); 7 } 8 }else{ 9 for(int i=size-1;i>index;i--){10 temp=temp.getPrevious();11 }12 }13 return temp;14 }
4、查询
1 public Object get(int index){2 checkRange(index);3 Node temp=null;4 if(null!=first){5 temp=node(index);6 }7 return temp.getObj();8 }
5、插入一个元素(头部插入、尾部插入、中间插入)
public void add(int index,Object obj){ checkRange(index); //移动指针，指向索引位置的节点 Node temp=node(index); //从中间任任意一个位置插入 if(first!=null){ //创建一个新节点 Node n=new Node(); //修改当前节点的前后节点 Node before=temp.getPrevious(); n.setPrevious(before); n.setNext(temp); n.setObj(obj); before.setNext(n); temp.setPrevious(n); } } public void add(Object obj){ Node n=new Node(); //如果队头为空从队头插入 if(first==null){ //初始状态:头尾指针指向第一个节点 n.setObj(obj); n.setPrevious(null); n.setNext(null); first=n; last=n; }else{ //从队尾部插入 n.setObj(obj); n.setPrevious(last); n.setNext(null); //上一个实现的next指向下一个节点 last.setNext(n); last=n; } size++; }
6、删除
1 public void remove(int index){ 2 checkRange(index); 3 if (null!=first){ 4 //遍历直到目标节点 5 Node temp=node(index); 6 Node befor=temp.getPrevious(); 7 Node after=temp.getNext(); 8 after.setPrevious(befor); 9 befor.setNext(after);10 size--;11 }12 }
7、源于揭秘LinkedList的核心部分，就没有赘述所有实现的方法。
JAVA容器-模拟LinkedList实现(双链表)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。