Ignite

Java中单链表的实现

2017-08-23

Java中我们使用的ArrayList,其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高,但是插入和删除时优势明显。下面对单向链表做一个介绍。

单向链表是一种线性表,实际上是由节点(Node)组成的,一个链表拥有不定数量的节点。其数据在内存中存储是不连续的,它存储的数据分散在内存中,每个结点只能也只有它能知道下一个结点的存储位置。由N各节点(Node)组成单向链表,每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点(Head),我们对链表的所有操作,都是直接或者间接地通过其头节点来进行的。

下面是具体的实现
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

package mylink;

/**
*
* Java中链表的创建及相关操作
*
* @author fisherman
*
*/
public class MyLink {
Node head = null;

class Node {
private int data;// 定义数据域
private Node next; // 定义指针域

public Node(int data) {
this.data = data;
}

}
/*
class NodeOther{
private int data;// 定义数据域
private Node next; // 定义指针域
public NodeOther(){
this.data= data;
}
}*/

/**
* 插入数据
*
* @param
*/
public void addNode(int data) {
Node node = new Node(data);
if (head == null) {
head = node;
return;
}
Node tmp = head;
while (tmp.next != null) { // 若下一个节点不为空,指针后移
tmp = tmp.next;
}

tmp.next = node; // 然后把新的节点添加
}

/**
* 计算链表的长度
*
* @return
*/
public int size() {
int size = 0;
Node tmp = head;
while (tmp != null) { // 若头结点不为空
size++; // 长度加一
tmp = tmp.next;// 指针后移一位,指向下一个节点,然后再进行循环,长度再加一
}
return size;
}

/**
* 删除序号为index的节点
*
* @param index
* @return
*/
public boolean deleteNode(int index) {
if (index < 1 || index > size())
return false; // 若所找节点的序号不存在 ,返回false
if (index == 1) {
head = head.next;
return true; // 若序号为1,说明找的是头结点
}
int i = 2; // 从第二个节点开始
Node preNode = head; // 初始为head 作为前驱节点
Node currNode = preNode.next; // 现在的节点为head的下一个节点
while (currNode != null) {

if (i == index) {
preNode.next = currNode.next; // 删除 currNode(当前节点)节点
return true;
}
preNode = currNode; // preNode节点变为下一个节点
currNode = currNode.next; // currNode节点变为下一个节点
i++; // 继续向后查找
}
return false;
}
/**
* 在不知道头指针的情况下删除指定节点
* @param node
* @return
*/
public boolean deleteNodeOther(Node node) {
if (node == null || node.next == null)
return false;
int temp = node.data;
node.data = node.next.data;// 把待删除节点下一节点的数据覆盖待删除节点数据
node.next.data = temp;// 保存了已删除节点的数据
node.next = node.next.next;
return true;

}

/**
* 打印链表
*
* @param
*/
public void printList() {
Node tmp = head;
while (tmp != null) {
System.out.println(tmp.data);
tmp = tmp.next;
}

}

public static void main(String[] args) {
MyLink link = new MyLink();
link.addNode(2);
link.addNode(3);
link.addNode(4);
link.addNode(5);
System.out.println("长度为:" + link.size());
link.printList();
System.out.println("删除第二个元素:" + link.deleteNode(2));
System.out.println("删除后长度为:" + link.size());
link.printList();
/* MyLink.NodeOther node=new MyLink().new NodeOther();
System.err.println("删除第三个节点:"+link.deleteNodeOther(node)); */
}

}
Tags: Java
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章