1 package com.ietree.basic.datastructure.dublinklist;  2   3 /**  4  * 双向链表  5  *   6  * @author Dylan  7  */  8 public class DuLinkList<T> {  9  10     // 定义一个内部类Node，Node实例代表链表的节点 11     private class Node { 12  13         // 保存节点的数据 14         private T data; 15         // 保存上个节点的引用 16         private Node prev; 17         // 指向下一个节点的引用 18         private Node next; 19  20         // 无参构造器 21         public Node() { 22         } 23  24         // 初始化全部属性的构造器 25         public Node(T data, Node prev, Node next) { 26  27             this.data =http://www.mamicode.com/ data; 28             this.prev = prev; 29             this.next = next; 30  31         } 32  33     } 34  35     // 保存该链表的头节点 36     private Node header; 37     // 保存该链表的尾节点 38     private Node tail; 39     // 保存该链表中已包含的节点数 40     private int size; 41  42     // 创建空链表 43     public DuLinkList() { 44  45         // 空链表，header和tail都是null 46         header = null; 47         tail = null; 48  49     } 50  51     // 以指定数据元素来创建链表，该链表只有一个元素 52     public DuLinkList(T element) { 53  54         header = new Node(element, null, null); 55         // 只有一个节点，header、tail都指向该节点 56         tail = header; 57         size++; 58  59     } 60  61     // 返回链表的长度 62     public int length() { 63  64         return size; 65  66     } 67  68     // 获取链式线性表中索引为index处的元素 69     public T get(int index) { 70  71         return getNodeByIndex(index).data; 72  73     } 74  75     // 根据索引index获取指定位置的节点 76     public Node getNodeByIndex(int index) { 77  78         if (index < 0 || index > size - 1) { 79  80             throw new IndexOutOfBoundsException("线性表索引越界"); 81  82         } 83         if (index <= size / 2) { 84  85             // 从header节点开始 86             Node current = header; 87             for (int i = 0; i <= size / 2 && current != null; i++, current = current.next) { 88                 if (i == index) { 89  90                     return current; 91  92                 } 93             } 94  95         } else { 96  97             // 从tail节点开始搜索 98             Node current = tail; 99             for (int i = size - 1; i > size / 2 && current != null; i++, current = current.prev) {100                 if (i == index) {101 102                     return current;103 104                 }105             }106 107         }108 109         return null;110     }111 112     // 查找链式线性表中指定元素的索引113     public int locate(T element) {114 115         // 从头结点开始搜索116         Node current = header;117         for (int i = 0; i < size && current != null; i++, current = current.next) {118 119             if (current.data.equals(element)) {120                 return i;121             }122 123         }124         return -1;125 126     }127 128     // 向线性链表的指定位置插入一个元素129     public void insert(T element, int index) {130 131         if (index < 0 || index > size) {132             throw new IndexOutOfBoundsException("线性表索引越界");133         }134 135         // 如果还是空链表136         if (header == null) {137 138             add(element);139 140         } else {141 142             // 当index为0时，也就是在链表头处插入143             if (index == 0) {144 145                 addAtHeader(element);146 147             } else {148 149                 // 获取插入点的前一个节点150                 Node prev = getNodeByIndex(index - 1);151                 // 获取插入点的节点152                 Node next = prev.next;153                 // 让新节点的next引用指向next节点，prev引用指向prev节点154                 Node newNode = new Node(element, prev, next);155                 // 让prev的next节点指向新节点156                 prev.next = newNode;157                 // 让prev的下一个节点的prev指向新节点158                 next.prev = newNode;159                 size++;160             }161 162         }163 164     }165 166     // 采用尾插法为链表添加新节点167     public void add(T element) {168 169         // 如果该链表还是空链表170         if (header == null) {171 172             header = new Node(element, null, null);173             // 只有一个节点，header、tail都指向该节点174             tail = header;175 176         } else {177 178             // 创建新节点，新节点的pre指向原tail节点179             Node newNode = new Node(element, tail, null);180             // 让尾节点的next指向新增的节点181             tail.next = newNode;182             // 以新节点作为新的尾节点183             tail = newNode;184 185         }186         size++;187     }188 189     // 采用头插法为链表添加新节点190     public void addAtHeader(T element) {191         // 创建新节点，让新节点的next指向原来的header192         // 并以新节点作为新的header193         header = new Node(element, null, header);194         // 如果插入之前是空链表195         if (tail == null) {196 197             tail = header;198 199         }200         size++;201     }202 203     // 删除链式线性表中指定索引处的元素204     public T delete(int index) {205 206         if (index < 0 || index > size - 1) {207 208             throw new IndexOutOfBoundsException("线性表索引越界");209 210         }211         Node del = null;212         // 如果被删除的是header节点213         if (index == 0) {214 215             del = header;216             header = header.next;217             // 释放新的header节点的prev引用218             header.prev = null;219 220         } else {221 222             // 获取删除节点的前一个节点223             Node prev = getNodeByIndex(index - 1);224             // 获取将要被删除的节点225             del = prev.next;226             // 让被删除节点的next指向被删除节点的下一个节点227             prev.next = del.next;228             // 让被删除节点的下一个节点的prev指向prev节点229             if (del.next != null) {230 231                 del.next.prev = prev;232 233             }234 235             // 将被删除节点的prev、next引用赋为null236             del.prev = null;237             del.next = null;238 239         }240         size--;241         return del.data;242     }243 244     // 删除链式线性表中最后一个元素245     public T remove() {246 247         return delete(size - 1);248 249     }250 251     // 判断链式线性表是否为空表252     public boolean empty() {253 254         return size == 0;255 256     }257 258     // 清空线性表259     public void clear() {260 261         // 将底层数组所有元素赋为null262         header = null;263         tail = null;264         size = 0;265 266     }267 268     public String toString() {269 270         // 链表为空链表271         if (empty()) {272 273             return "[]";274 275         } else {276 277             StringBuilder sb = new StringBuilder("[");278             for (Node current = header; current != null; current = current.next) {279 280                 sb.append(current.data.toString() + ", ");281 282             }283             int len = sb.length();284             return sb.delete(len - 2, len).append("]").toString();285 286         }287 288     }289 290     // 倒序toString291     public String reverseToString() {292 293         if (empty()) {294 295             return "[]";296 297         } else {298 299             StringBuilder sb = new StringBuilder("[");300             for (Node current = tail; current != null; current = current.prev) {301 302                 sb.append(current.data.toString() + ", ");303 304             }305             int len = sb.length();306             return sb.delete(len - 2, len).append("]").toString();307 308         }309 310     }311 312 }

 1 package com.ietree.basic.datastructure.dublinklist; 2  3 /** 4  * 测试类 5  *  6  * @author Dylan 7  */ 8 public class DuLinkListTest { 9 10     public static void main(String[] args) {11 12         DuLinkList<String> list = new DuLinkList<String>();13         list.insert("aaaa", 0);14         list.add("bbbb");15         list.insert("cccc", 0);16         // 在索引为1处插入一个新元素17         list.insert("dddd", 1);18         // 输出顺序线性表的元素19         System.out.println(list);20         // 删除索引为2处的元素21         list.delete(2);22         System.out.println(list);23         System.out.println(list.reverseToString());24         // 获取cccc字符串在顺序线性表中的位置25         System.out.println("cccc在顺序线性表中的位置：" + list.locate("cccc"));26         System.out.println("链表中索引1处的元素：" + list.get(1));27         list.remove();28         System.out.println("调用remove方法后的链表：" + list);29         list.delete(0);30         System.out.println("调用delete(0)后的链表：" + list);31 32     }33 34 }

[cccc, dddd, aaaa, bbbb][cccc, dddd, bbbb][bbbb, dddd, cccc]cccc在顺序线性表中的位置：0链表中索引1处的元素：dddd调用remove方法后的链表：[cccc, dddd]调用delete(0)后的链表：[dddd]