Java链表实现

1package MyLinkedListDemo;
2
3import java.util.Scanner;
4
5public class MyLinkedListDemo {
6    public static void main(String[] args) {
7        Scanner in = new Scanner(System.in);
8        MyLinkedList<Integer> list = new MyLinkedList<Integer>();
9        list.add(-1, 1);
10        list.add(-1, 2);
11        list.add(-1, 3);
12        list.add(-1, 4);
13        list.add(-1, 5);
14        int a = list.get(2);
15        System.out.println(a);
16        in.close();
17        }
18    }
19
20    class MyLinkedList<T> {
21
22        //链表总长度
23        int len = 0;
24        // 头节点
25        Node head = null;
26        // 尾节点
27        Node end = null;
28
29        // 链表节点类（内部类）
30        class Node {
31            // 上一个节点
32            Node prev;
33            // 下一个节点
34            Node next;
35            // 数据块
36            T data;
37
38            // 空构造器，用于构造临时节点和定位节点等不需要使用数据块的节点
39            Node() {
40            };
41
42            // 可填入数据的构造器，用填入数据
43            Node(T data) {
44                // 填入数据到数据块
45                this.data = data;
46            }
47        }
48
49        // 插入链表节点的方法
50        // 参数i ： 表示要插入的位置，当 i = -1 时新节点会被放置头位置，若 i = -2 时新节点会被放置至尾位置
51        public void add(int i /* 要添加的位置，新节点会添加至该位置之后 */, T data /* 传入数据 */) {
52            // 递增定位
53            len++;
54            int j;
55            // 定义定位节点
56            Node indexNode = head;
57            // 创建新节点
58            Node newNode = new Node(data);
59
60            // 判断链表是否为空
61            if (head == null) {
62                // 若是只需将新节点设为头节点和尾节点就行
63                head = newNode;
64                end = newNode;
65                return;
66            }
67
68            // Create Mode
69            if (i == -1) // 头插法
70            {
71                newNode.next = head;
72                head.prev = newNode;
73                head = newNode;
74                return;
75            } else if (i == -2) // 尾插法
76            {
77                while (indexNode.next != null) {
78                    indexNode = indexNode.next;
79                }
80            }
81
82            // Insert Mode
83
84            // 移动定位节点至指定位置
85            for (j = 0; j < i && indexNode != null; j++) {
86                indexNode = indexNode.next;
87            }
88            // 判断是否是添加至最后一个节点
89            if (indexNode.next == null) {
90                // 将上一个节点next指向新节点
91                indexNode.next = newNode;
92                // 将新节点的prev指向上一个节点
93                newNode.prev = indexNode;
94                // 将新节点的next指向null
95                newNode.next = null;
96                // 将新节点设为尾节点
97                end = newNode;
98                return;
99            }
100            // 创建临时节点用于存储原下一个节点的地址
101            Node tempNode = indexNode.next;
102            // 将上一个节点的next指向新节点
103            indexNode.next = newNode;
104            // 将新节点的next指向原下一个节点
105            newNode.next = tempNode;
106            // 将新节点的prev指向上一个节点
107            newNode.prev = indexNode;
108            // 将原下一个节点的prev指向新节点
109            tempNode.prev = newNode;
110        }
111
112        // 插入带数据的链表到指定位置,操作方式同add，只是新增的节点是已经有数据的
113        public void add(int i, Node haveNode) {
114            len++;
115            int j;
116            Node indexNode = head;
117
118            if (i == -1) {
119                haveNode.next = head;
120                head.prev = haveNode;
121                head = haveNode;
122                return;
123            }
124
125            for (j = 0; j < i && indexNode != null; j++) {
126                indexNode = indexNode.next;
127            }
128
129            if (indexNode.next == null) {
130                indexNode.next = haveNode;
131                haveNode.prev = indexNode;
132                haveNode.next = null;
133                end = haveNode;
134                return;
135            }
136
137            haveNode.next = indexNode.next;
138            haveNode.next.prev = haveNode;
139            haveNode.prev = indexNode;
140            indexNode.next = haveNode;
141        }
142
143        // 删除指定节点
144        // 参数 i ： 当 i = 0 时代表删除第一个节点，i = -1 时代表删除最后一个节点
145        public void delete(int i/* 要删除节点的位置 */) {
146            len--;
147            // 判断是否是删除第一个节点
148            if (i == 0) {
149                // 将头节点指向第二个节点，然后将头节点的prev设置为null，这样就屏蔽掉了第一个节点
150                head = head.next;
151                head.prev = null;
152                return;
153            }
154            // 若是删除最后一个节点，那只需将尾节点移到倒数第二个节点即可
155            else if (i == -1) {
156                end = end.prev;
157                end.next = null;
158                return;
159            }
160
161            // 递增定位
162            int j;
163            // 创建定位节点，将其指向头节点
164            Node indexNode = head;
165            // 将定位节点移至要删除节点的上一个节点
166            for (j = 0; j < i - 1 && indexNode != null; j++) {
167                indexNode = indexNode.next;
168            }
169            // 判断要删除节点是否是最后一个节点
170            if (indexNode.next.next == null) {
171                // 操作方式同删除头节点与
172                end = end.prev;
173                end.next = null;
174                return;
175            }
176            // 要删除节点的下一个节点prev设置为要删除节点的上一个节点
177            indexNode.next.next.prev = indexNode;
178            // 将要删除节点的上一个节点的next设置为要删除节点的下一个节点
179            indexNode.next = indexNode.next.next;
180        }
181
182        // 清空链表
183        public void clear() {
184            len = 0;
185            // 清空链表只需将头节点和尾节点设置为null即可，内存会由垃圾回收器回收
186            head = null;
187            end = null;
188        }
189
190        // 遍历输出链表数据
191        public void print() {
192            // 创建定位节点
193            Node indexNode = head;
194            // 使用while循环进行遍历
195            while (indexNode != null) {
196                // 输出数据
197                System.out.print(indexNode.data.toString() + " ");
198                // 移动定位节点
199                indexNode = indexNode.next;
200            }
201            // 换行
202            System.out.println();
203        }
204
205        // 链表逆置
206        public void resever() {
207            // 创建临时节点用来临时存储指向数据
208            Node tempNode = new Node();
209            // 将头节点与尾节点交换
210            tempNode = head;
211            head = end;
212            end = tempNode;
213            // 创建定位节点
214            Node indexNode = head;
215            // 循环交换next和prev数据
216            while (indexNode.prev != null && (indexNode.next != null || indexNode == head)) {
217                tempNode = indexNode.next;
218                indexNode.next = indexNode.prev;
219                indexNode.prev = tempNode;
220                indexNode = indexNode.next;
221            }
222            // 设置最后一个节点的next为null
223            end.next = null;
224            // 设置最后一个节点的prev数据
225            end.prev = tempNode.next;
226        }
227
228        // 添加新节点到列表末尾
229        public void addFirst(T data) {
230            this.add(-2, data);
231        }
232
233        // 添加新节点到列表头
234        public void addLast(T data) {
235            this.add(-1, data);
236        }
237
238        // 获取指定位置的数据
239        public T get(int i) {
240            Node indexNode = head;
241            for (int j = 0; j < i; j++) {
242                indexNode = indexNode.next;
243            }
244            return indexNode.data;
245        }
246
247    }