何谓链表

  • 在物理存储上非连续、非顺序的存储结构。
  • 数据之间通过指针关联。
  • data（数据）、next（指针）

特点

  • 物理空间不连续，内存开销较大（存储指针）。
  • 无容量限制。
  • 查找元素需要顺序遍历。
  • 操作复杂。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
package linkedlist;
/**
 *	链表实现
 */
public class LinkedList {
	public Node head = null; // 头节点
	public Node tail = null; // 尾节点
	public int size = 0;
	// 头插入
	public boolean insertHead(Object data) {
		if (size == 0) {
			initial(data);
		} else {
			Node node = new Node(data);
			node.setNext(head);
			head = node;
		}
		size++;
		return true;
	}
	// 尾插入
	public boolean insertTail(Object data) {
		if (size == 0) {
			initial(data);
		} else {
			Node node = new Node(data);
			tail.setNext(node);
			tail = node;
		}
		size++;
		return true;
	}
	// 中间插入,插入到index的后面
	public boolean insertAfter(int index, Object data) throws Exception {
		if (index > size) {
			insertTail(data);
		} else {
			if (index == 0) {
				insertHead(data);
			} else {
				// 获得index对应的node
				Node indexNode = getByIndex(index);
				Node node = new Node(data);
				node.setNext(indexNode.getNext());
				indexNode.setNext(node);
				size++;
			}
		}
		return true;
	}
	// 头删除
	public boolean removeHead() throws Exception {
		if (size == 0) {
			throw new Exception("likedlist is empty , can not remove head node");
		}
		head.setData(head.getNext().getData());
		head.setNext(head.getNext().getNext());
		size--;
		return true;
	}
	// 尾删除
	public boolean removeTail() throws Exception {
		if (size == 0) {
			throw new Exception("likedlist is empty , can not remove tail node");
		}
		size--;
		Node newTail = getByIndex(size);
		newTail.setNext(null);
		return true;
	}
	// 中间删除
	public boolean removeIndex(int index) throws Exception {
		if (size == 0) {
			throw new Exception("likedlist is empty , can not remove any node");
		}
		Node indexNode = getByIndex(index);
		indexNode.setData(indexNode.getNext().getData());
		indexNode.setNext(indexNode.getNext().getNext());
		size--;
		return true;
	}
	// 查找
	public Node getByIndex(int index) throws Exception {
		if (index > size) {
			throw new Exception("list is out by index " + index);
		}
		Node result = head;
		for (int i = 2; i <= index; i++) {
			result = result.getNext();
		}
		return result;
	}
	// 初始化第一个元素
	public void initial(Object data) {
		Node n = new Node(data);
		head = n;
		tail = n;
	}
    //遍历
	public void traverse() {
		Node tmp = head;
		while (tmp != null) {
			System.out.println(tmp.getData());
			tmp = tmp.getNext();
		}
	}
	
	// 反转
	public void reverse() {
		Node tmp = head;
		Node tmp1 = tmp.getNext();
		for (int i = 0; i < size - 1; i++) {
			Node tmp2 = tmp1.getNext();
			tmp1.setNext(tmp);
			tmp = tmp1;
			tmp1 = tmp2;
		}
		head.setNext(null);
		head = tmp;
	}
}
// 节点
class Node {
	private Object data;
	private Node next;
	public Node() {
	}
	public Node(Object data) {
		super();
		this.data = data;
	}
	public Object getData() {
		return data;
	}
	public void setData(Object data) {
		this.data = data;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
}