链表-单向链表的实现

69 阅读 0 评论 46 点赞

我是靠谱客的博主难过板凳，这篇文章主要介绍链表-单向链表的实现，现在分享给大家，希望可以做个参考。

单向链表的实现重点在

1. 定义节点，数据变量及指向下一个指针的变量

2. 定义链表类头结点变量,初始化时默认为null

3. 搜索下标值，循环遍历下标个节点，获取节点的值

4. 插入头结点, 创建新节点，将新节点的下一个节点指向头结点，头结点指向新节点

5. 插入尾结点，循环遍历到最后一个节点，最后一个节点的下一个节点执行新节点

6. 插入指定下标节点, 循环遍历下标-1个节点，创建新节点，将新节点的下一个节点指向目标位置的前一个节点的下一个节点，将目标位置的前一个节点的下一个节点指向新节点

7. 删除执行下标节点, 循环遍历下标-1个节点，将下标-1个节点的下一个节点执行目标位置前一个节点的下一个节点的下一个节点

复制代码

public class MyLinkedList {
/**
* 定义列表节点, 包括节点的数据及指向下一个节点的指针
*/
class Node{
int val;
Node next;
public Node(int val){
this.val = val;
}
}
/**
* 定义头结点
*/
Node head;
/**
* 初始化头结点
*/
public MyLinkedList() {
this.head = null;
}
/**
* 获取指定下标值
* @param index
* @return
*/
public int get(int index) {
// 如果下标不合法，则直接返回-1
if(index<0){
return -1;
}
// 定义临时节点存储头结点
Node p = head;
// 循环遍历 下标 个 节点
for(int i=0;i<index && p!=null;i++){
p = p.next;
}
// 如果已经越界则返回-1
if(p==null){
return -1;
}
// 如果有对应下标的节点，则返回对应值
return p.val;
}
/**
* 在头结点插入节点
* @param val
*/
public void addAtHead(int val) {
// 创建新节点
Node node = new Node(val);
// 将新节点的下一个节点指向头结点
node.next = head;
// 头结点指向新节点
head = node;
}
/**
* 在尾部插入节点
* @param val
*/
public void addAtTail(int val) {
// 如果头结点为空，则直接赋值头结点
if(head==null){
head = new Node(val);
return;
}
// 创建临时节点指向头结点
Node p =head;
// 循环下一个节点直至下一个节点为空
while(p.next!=null){
p = p.next;
}
// 下一个节点指向新节点
p.next = new Node(val);
}
/**
* 指定下标插入节点
* @param index
* @param val
*/
public void addAtIndex(int index, int val) {
// 如果下标小于等于0，则插入头部
if(index<=0){
addAtHead(val);
return;
}
// 定义长度变量
int len=0;
// 定义临时节点执行头结点
Node p = head;
// 遍历所有节点至最后获取长度
while(p!=null){
p = p.next;
len++;
}
// 如果下标等于链表长度，则插入链尾
if(len == index){
addAtTail(val);
return;
}
// 如果下标超过链表长度，则不处理
if(index > len){
return;
}
//定义临时节点指向头结点
p = head;
// 循环遍历下标个-1个节点，获取目标位置的前节点
for(int i=0;i<index-1;i++){
p = p.next;
}
// 定义新节点
Node node = new Node(val);
// 将新节点的下一个节点执行目标位置前一个节点的下一个节点
node.next = p.next;
// 将目标节点的前一个节点指向新节点
p.next = node;
}
/**
* 删除执行下标节点
* @param index
*/
public void deleteAtIndex(int index) {
// 定义长度变量
int len = 0;
// 定义临时节点变量指向头节点
Node p = head;
// 循环遍历获取长度
while (p!=null){
len++;
p = p.next;
}
// 如果删除下标合法范围内, 则给予处理
if(index>=0 &&index<len){
// 如果删除为头部，则直接将头结点指向下一个节点
if(index == 0){
head = head.next;
return;
}
// 定义临时节点变量指向头结点
p=head;
// 循环遍历 下标-1个节点
for(int i=0;i<index-1;i++){
p = p.next;
}
// 将删除目标位置的前一个节点的下一个节点指向
// 前一个节点的下一个节点的下一个节点
p.next = p.next.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
public class MyLinkedList {
/**
* 定义列表节点, 包括节点的数据及指向下一个节点的指针
*/
class Node{
int val;
Node next;
public Node(int val){
this.val = val;
}
}
/**
* 定义头结点
*/
Node head;
/**
* 初始化头结点
*/
public MyLinkedList() {
this.head = null;
}
/**
* 获取指定下标值
* @param index
* @return
*/
public int get(int index) {
// 如果下标不合法，则直接返回-1
if(index<0){
return -1;
}
// 定义临时节点存储头结点
Node p = head;
// 循环遍历 下标 个 节点
for(int i=0;i<index && p!=null;i++){
p = p.next;
}
// 如果已经越界则返回-1
if(p==null){
return -1;
}
// 如果有对应下标的节点，则返回对应值
return p.val;
}
/**
* 在头结点插入节点
* @param val
*/
public void addAtHead(int val) {
// 创建新节点
Node node = new Node(val);
// 将新节点的下一个节点指向头结点
node.next = head;
// 头结点指向新节点
head = node;
}
/**
* 在尾部插入节点
* @param val
*/
public void addAtTail(int val) {
// 如果头结点为空，则直接赋值头结点
if(head==null){
head = new Node(val);
return;
}
// 创建临时节点指向头结点
Node p =head;
// 循环下一个节点直至下一个节点为空
while(p.next!=null){
p = p.next;
}
// 下一个节点指向新节点
p.next = new Node(val);
}
/**
* 指定下标插入节点
* @param index
* @param val
*/
public void addAtIndex(int index, int val) {
// 如果下标小于等于0，则插入头部
if(index<=0){
addAtHead(val);
return;
}
// 定义长度变量
int len=0;
// 定义临时节点执行头结点
Node p = head;
// 遍历所有节点至最后获取长度
while(p!=null){
p = p.next;
len++;
}
// 如果下标等于链表长度，则插入链尾
if(len == index){
addAtTail(val);
return;
}
// 如果下标超过链表长度，则不处理
if(index > len){
return;
}
//定义临时节点指向头结点
p = head;
// 循环遍历下标个-1个节点，获取目标位置的前节点
for(int i=0;i<index-1;i++){
p = p.next;
}
// 定义新节点
Node node = new Node(val);
// 将新节点的下一个节点执行目标位置前一个节点的下一个节点
node.next = p.next;
// 将目标节点的前一个节点指向新节点
p.next = node;
}
/**
* 删除执行下标节点
* @param index
*/
public void deleteAtIndex(int index) {
// 定义长度变量
int len = 0;
// 定义临时节点变量指向头节点
Node p = head;
// 循环遍历获取长度
while (p!=null){
len++;
p = p.next;
}
// 如果删除下标合法范围内, 则给予处理
if(index>=0 &&index<len){
// 如果删除为头部，则直接将头结点指向下一个节点
if(index == 0){
head = head.next;
return;
}
// 定义临时节点变量指向头结点
p=head;
// 循环遍历 下标-1个节点
for(int i=0;i<index-1;i++){
p = p.next;
}
// 将删除目标位置的前一个节点的下一个节点指向
// 前一个节点的下一个节点的下一个节点
p.next = p.next.next;
}
}
}