1 public class ListExer2 {
2 public static void main(String[] args) {
3 LinkList list = new LinkList();
4 list.add("a");
5 list.add("b");
6 list.add("c");
7 // list.add(0,"d");
8 // list.add(1, "e");
9 // list.remove(0);
10 // list.remove(2);
11 list.remove(1);
12 System.out.println(list);
13 }
14 }
15
16 class LinkList {
17 private int size = 0; // 节点个数
18 private Node first; // 第一个节点
19 private Node last; // 最后一个节点
20
21 public LinkList() {
22 }
23
24 public void add(String str) {
25 // 创建节点存储数据
26 Node node = new Node(null, str, null);
27
28 // 列表此时为空
29 if (size == 0) {
30 // 如果列表为空，则头结点指向新节点
31 this.first = node;
32 } else {
33 // 原来的尾节点的下一位置为新节点
34 this.last.next = node;
35 // 新节点的上一位是原来的尾节点
36 node.prev = this.last;
37 }
38 // 新的节点变成了尾节点
39 this.last = node;
40 size++;
41 }
42
43 public void add(int index, String str) {
44 // 判断下标是否越界
45 if (index > size)
46 throw new IndexOutOfBoundsException("Index:" + index + ", Size:"
47 + size);
48 // 在尾部追加
49 if (index == size) {
50 this.add(str);
51 return;
52 }
53 Node node = new Node(null, str, null);
54 // 插入的头部
55 if (index == 0) {
56 node.next = this.first;
57 this.first.prev = node;
58 this.first = node;
59 } else {
60
61 Node no = this.getNode(index);
62
63 // 原节点的上一个节点的下一位变成新的节点
64 no.prev.next = node;
65 // 新的节点的上一位是原节点的上一位
66 node.prev = no.prev;
67 // 新节点的下一位是原来的节点
68 node.next = no;
69 // 原节点的上一位是新的节点
70 no.prev = node;
71
72 }
73 size++;
74 }
75
76 private Node getNode(int index) {
77 // 获取指定位置的节点
78 Node no = this.first;
79 for (int i = 0; i < index; i++) {
80 no = no.next;
81 }
82 return no;
83 }
84
85 private void out(int index) {
86 // 判断下标越界
87 if (index >= size)
88 throw new IndexOutOfBoundsException("Index:" + index + ", Size:"
89 + size);
90
91 }
92
93 public void remove(int index) {
94
95 this.out(index);
96 // 头部
97 if (index == 0) {
98 this.first = this.first.next;
99 this.first.prev = null;
100 } /* 尾部 */else if (index == size - 1) {
101 this.last = this.last.prev;
102 this.last.next = null;
103 } else {
104 Node node = this.getNode(index);
105
106 // 原节点的上一个节点的下一位变成原节点的下一位
107 node.prev.next = node.next;
108 // 原节点的下一个节点的上一位变成原节点的上一位
109 node.next.prev = node.prev;
110 }
111 size--;
112 }
113
114 public int indexOf(String str) {
115
116 Node node = this.first;
117 for (int i = 0; i < size; i++) {
118 String data = node.data;
119 if (data == str || data != null && data.equals(str))
120 return i;
121 node = node.next;
122 }
123
124 return -1;
125
126 }
127
128 public String toString() {
129
130 StringBuilder sb = new StringBuilder("[");
131 Node node = this.first;
132 for (int i = 0; i < size; i++) {
133 sb.append(node.data).append(", ");
134 node = node.next;
135 }
136
137 String str = sb.toString();
138 if (size > 0)
139 str = str.substring(0, str.length() - 2);
140 return str += "]";
141 }
142
143 // 利用节点存储数据
144 private class Node {
145 Node prev; // 上一个节点
146 String data; // 元素
147 Node next; // 下一个节点
148 public Node(Node prev, String data, Node next) {
149 super();
150 this.prev = prev;
151 this.data = data;
152 this.next = next;
153 }
154
155 }
156
157 }
