LinkedList : 双向链表与实现

所谓双向链表：

（由此图可见老夫深厚的画功）

链表，就是由一个一个的节点连接组成。

在这里，每一个节点都是由三部分组成：上一个节点、当前节点的元素、下一个节点

当链表中只有一个节点的时候，这个节点指向的上一个节点是空的，下一个节点也是空的

当有多个节点的时候，第一个节点的上一个节点是空的，最后一个节点的下一个节点也是空的。

如上图：A节点的下一个节点指向了B节点，B节点的上一个节点指向了A节点

不说了...鉴于本人的表达能力不是很强...还是直接上代码吧...

 1 public class MyLinkedList { 2   /*第一个节点*/ 3   private Node first; 4   /*最后一个节点*/ 5   private Node last; 6   /*大小*/ 7   private int size; 8   /** 9    * 获取这个链表的大小（元素的个数） 10    * @return  11   */ 12   public int size(){ 13     return size; 14   } 15   /** 16    * 这个方法是从LinkedList.node(index)方法中复制过来的，稍加修改 17    * 用于返回指点下标处的节点 18    * @return 19   */ 20   private Node node(int index){ 21     /* 22      * 打个比方： 23      * size = 6; 24      * size >> 1 = 3 25      * 如果index小于3的话，就从第一个找到最后一个 26      * 如果index大于3的话，就从最后一个找到第一个 27      * 下面代码亦是如此 28     */ 29     if (index < (size >> 1)) { 30       Node x = first; 31       for (int i = 0; i < index; i++) 32         x = x.next; 33       return x; 34     } else { 35       Node x = last; 36       for (int i = size - 1; i > index; i--) 37         x = x.prev; 38       return x; 39     } 40   } 41   /** 42    * 增加一个节点 43    * @param obj 要增加的元素 44   */ 45   public void add(Object obj){ 46     Node temp = new Node();//新的节点 47     /*新节点的元素赋值*/ 48     temp.element = obj; 49      50     if (first==null) {//如果第一个节点是空的，那就是没有节点 51       //这个节点既然是第一个节点，所以节点的prev点和next都是空的，所以，不用赋值 52       //同理，这个新插入的节点是第一个，也是最后一个 53       first = temp; 54       last = temp; 55     }else {//否则，那就意味着这个节点不是空的。 56       //新节点的prev就是在这个节点插入前的最后一个节点 57       temp.prev = last; 58       //而插入前的最后一个节点的next就是这个新的节点了 59       //这样，就会形成一条链:a的下一个是b，b的上一个是a，a的下一个是b...... 60       last.next = temp; 61       //最后，新的节点就是最后一个节点了 62       last = temp; 63     } 64     //插入成功size++; 65     size++; 66   } 67   /** 68    * 增加一个节点，指定位置 69    * @param index 70    * @param obj 71   */ 72   public void add(int index, Object obj){ 73     Node temp = node(index);//得到的节点 74     Node newNode = new Node();//新的节点 75     newNode.element = obj; 76      77     if (temp!=null) {//如果得到的指定节点不是空的话 78       //得到temp的上一个节点 79       Node tempPrev = temp.prev; 80        81        82       //tempPrev的下一个节点赋值为newNode 83       tempPrev.next = newNode; 84       //同时，newNode的上一个节点赋值为tempPrev 85       newNode.prev = tempPrev; 86        87        88       //然后newNode的下一个节点便是这个一开始就指定的temp节点 89       newNode.next = temp; 90       //temp的上一个节点赋值为newNode 91       //这样在指定元素之前插入了一个新的元素 92       temp.prev = newNode; 93     } 94     size++; 95   } 96   /** 97    * 删除 98    * @param index 99   */100   public void remove(int index){101     /*102      * 删除...103      * 有 a b c三个元素104      * a的下一个节点是b b的下一个节点是c105      * c的上一个节点是b b的上一个节点是a106      * --107      * 比如删除了b108      * 那就要把a 和 c 连接起来。109      * 110      * 连接好了后，就是：111      * a 下一个节点是 c112      * c 上一个节点是 a113      * 114     */115     116     Node temp = node(index);//得到指定下标的元素117     if (temp!=null) {118       /*119       120       //得到temp的上一个节点121       Node tempPrev = temp.prev;122       //得到temp的下一个节点123       Node tempNext = temp.next;124       //tempPrev的下一个节点是tempNext125       tempPrev.next = tempNext;126       //而tempNext的上一个节点就是tempPrev127       tempNext.prev = tempPrev;128       129       */130       131       //temp的上一个节点的下一个节点就是temp的下一个节点132       temp.prev.next = temp.next;133       //temp的下一个节点的上一个节点就是temp的上一个节点134       temp.next.prev = temp.prev;135     }136     size--;137   }138   /**139    * 根据下标获取元素140    * @param index 元素的索引141    * @return142   */143   public Object get(int index){144     return node(index).element;//得到指定节点的元素145   }146   /*------------------------------------------------------------*/147   public static void main(String[] args) {148     MyLinkedList list = new MyLinkedList();149     list.add("a");150     list.add("b");151     list.add(1,"B");152     list.remove(1);153     System.out.println(list.get(1));154     System.out.println("当前链表的大小："+list.size());155   }156 }157 /**158  * 节点类159 */160 class Node{161   /*162    * 表示上一个节点163    * 所以使用节点类型164   */165   Node prev;166   /*表示下一个节点*/167   Node next;168   /*当前节点的元素*/169   Object element;170   171   public Node() {172   }173 174   public Node(Node prev, Node next, Object element) {175     this.prev = prev;176     this.next = next;177     this.element = element;178   }179   180 }

原标题：LinkedList : 双向链表与实现

关键词：