双向链表

  1 public class Demo {
  2     public static void main(String[] args) {
  3         MyLinkedList linkedList = new MyLinkedList();
  4         // 添加
  5         linkedList.add("123");
  6         linkedList.add("aaa");
  7         linkedList.add("中国人");
  8         System.out.println("获取长度为：" + linkedList.getSize());
  9         System.out.println("获取第0个元素：" + linkedList.getNode(0));
 10         System.out.println("打印全部链表元素：" + linkedList);
 11         // 添加到最前
 12         linkedList.addFirst("ccc");
 13         System.out.println("在最前面添加ccc之后打印链表元素：" + linkedList);
 14         // 添加到最后
 15         linkedList.addLast("zzz");
 16         System.out.println("在最后面添加zzz之后打印链表元素：" + linkedList);
 17         // 添加到指定位置
 18         linkedList.add(4, "ggg");
 19         System.out.println("在第4个位置添加ggg之后打印链表元素：" + linkedList);
 20         // 移除最前的
 21         linkedList.removeFirst();
 22         System.out.println("移除最前面的元素之后打印链表元素：" + linkedList);
 23         // 移除最后的
 24         linkedList.removeLast();
 25         System.out.println("移除最后面的元素之后打印链表元素：" + linkedList);
 26         // 移除指定位置上的
 27         linkedList.remove(2);
 28         System.out.println("移除第二个位置上的元素之后打印链表元素：" + linkedList);
 29         // 返回指定位置上的元素
 30         System.out.println("返回第一个位置上的元素：" + linkedList.getNode(1));
 31         System.out.println("完成所有操作之后打印链表元素：" + linkedList);
 32     }
 33 }
 34 class MyLinkedList implements MyMethods {
 35     private Node head = new Node(null);
 36     private int size;
 37     @Override
 38     public boolean add(String data) {
 39         addLast(data);
 40         return true;
 41     }
 42     @Override
 43     public boolean add(int index, String data) {
 44         if (index < 0 || index >= getSize())
 45             throw new NullPointerException("操作失败！");
 46         firstAdd(new Node(data), getNode(index));
 47         return true;
 48     }
 49     private void firstAdd(Node node, Node temp) {
 50         node.next = temp;
 51         node.prev = temp.prev;
 52         node.prev.next = node;
 53         node.next.prev = node;
 54         size++;
 55     }
 56     @Override
 57     public boolean addFirst(String data) {
 58         firstAdd(new Node(data), getNode(0));
 59         return true;
 60     }
 61     @Override
 62     public boolean addLast(String data) {
 63         lastAdd(data);
 64         return true;
 65     }
 66     private void lastAdd(String data) {
 67         if (getSize() == 0) {
 68             Node newNode = new Node(data);
 69             newNode.prev = head;
 70             newNode.prev.next = newNode;
 71             size++;
 72         } else {
 73             Node temp = getNode(getSize() - 1);
 74             Node node = new Node(data);
 75             node.prev = temp;
 76             node.prev.next = node;
 77             size++;
 78         }
 79     }
 80     @Override
 81     public int getSize() {
 82         return size;
 83     }
 84     @Override
 85     public boolean remove(int index) {
 86         if (index < 0 || index >= getSize())
 87             throw new NullPointerException("操作失败！");
 88         removeNodeFirst(getNode(index));
 89         return true;
 90     }
 91     @Override
 92     public boolean removeFirst() {
 93         removeNodeFirst(head.next);
 94         return true;
 95     }
 96     private void removeNodeFirst(Node node) {
 97         node.prev.next = node.next;
 98         node.next.prev = head;
 99         node.next = null;
100         node.prev = null;
101         size--;
102     }
103     @Override
104     public boolean removeLast() {
105         removeNodeLast(getNode(getSize() - 1));
106         return true;
107     }
108     private void removeNodeLast(Node node) {
109         node.prev.next = null;
110         node.prev = null;
111         size--;
112     }
113     @Override
114     public Node getNode(int index) {
115         Node node = head;
116         if (index < 0 || index >= getSize())
117             throw new NullPointerException("操作失败！");
118         for (int i = -1; i < index; i++) {
119             node = node.next;
120         }
121         return node;
122     }
123     class Node {
124         private String data;
125         private Node prev;
126         private Node next;
127         public Node(String data) {
128             this.data = data;
129         }
130         @Override
131         public String toString() {
132             return data;
133         }
134     }
135     @Override
136     public String toString() {
137         StringBuffer sb = new StringBuffer();
138         Node node = head;
139         for (int i = 0; i < size; i++) {
140             node = node.next;
141             if (i > 0)
142                 sb.append(",");
143             sb.append(node.data);
144         }
145         return sb.toString();
146     }
147 }
148 interface MyMethods {
149     // 添加元素
150     public boolean add(String data);
151     // 添加元素到最前面
152     public boolean addFirst(String data);
153     // 添加元素到最后面
154     public boolean addLast(String data);
155     // 在指定位置添加元素
156     public boolean add(int index, String data);
157     // 移除最前面的元素
158     public boolean removeFirst();
159     // 移除最后面的元素
160     public boolean removeLast();
161     // 移除指定位置上的元素
162     public boolean remove(int index);
163     // 获取指定位置上的元素
164     public Node getNode(int index);
165     // 获取链表的长度
166     public int getSize();
167 }

　　执行结果：

 1 获取长度为：3
 2 获取第0个元素：123
 3 打印全部链表元素：123,aaa,中国人
 4 在最前面添加ccc之后打印链表元素：ccc,123,aaa,中国人
 5 在最后面添加zzz之后打印链表元素：ccc,123,aaa,中国人,zzz
 6 在第4个位置添加ggg之后打印链表元素：ccc,123,aaa,中国人,ggg,zzz
 7 移除最前面的元素之后打印链表元素：123,aaa,中国人,ggg,zzz
 8 移除最后面的元素之后打印链表元素：123,aaa,中国人,ggg
 9 移除第二个位置上的元素之后打印链表元素：123,aaa,ggg
10 返回第一个位置上的元素：aaa
11 完成所有操作之后打印链表元素：123,aaa,ggg