java实现单链表

还是发现 网上java实现的很乱很杂。自己实现了一个单链表。主要操作 就是 单链表的头插法、尾插法

链表是一种插入和删除都比较快的数据结构,缺点是查找比较慢。

结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class MyLinkedList {
private Node head = new Node();// 头结点
static class Node {
int data; // 数据域
Node next; // 指针域
public Node(int data) {
this.data = data;
next = null;
}
public Node() {
next = null;
}
}
}

功能实现

头插法建表

1
2
3
4
5
6
7
8
9
10
11
12
13
// 头插法建表
public Node createList1(int... data){
if(data == null || data.length < 1)
throw new RuntimeException("数据为空");
for (int i=0; i<data.length; i++){
int value = data[i];
Node newNode = new Node(value);
Node p = head.next;
newNode.next = p;
head.next = newNode;
}
return head;
}

##尾插法建表

1
2
3
4
5
6
7
8
9
10
11
12
13
// 尾插法建表、需要增加一个 尾指针 引用
public void createList2(int... data){
Node tail = head;
if(data == null || data.length < 1)
throw new RuntimeException("数据为空");
for (int i=0; i<data.length; i++){
int value = data[i];
Node newNode = new Node(value);
tail.next = newNode;
tail = newNode;
}
tail.next = null;
}

第i个位置插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 在第i个位置上面 插入节点  1,2,3,4  在第2个位置 插入10  变为 1,10,2,3,4
public void insert(int i,int value){
Node p = head;
int index = 0;
int length = 0;
while (p.next != null){
p = p.next;
length++;
}
p = head;

if(i < 1 || i > length+1)
throw new RuntimeException("插入位置不合法");
while (index < i-1){
p = p.next;
index++;
}
Node newNode = new Node(value);
newNode.next = p.next;
p.next = newNode;
}

遍历

1
2
3
4
5
6
7
8
public void display(){
Node p = head;
while (p.next != null){
System.out.print(p.next.data+" ");
p = p.next;
}
System.out.println();
}