算法——线性表之链式存储结构单链表：有序链表：双向链表：

单链表：

概念：

1、由于线性表的顺序存储在插入与删除时需要移动大量元素，适用于不经常改变元素的情况，那么当我们需要经常操作元素时该怎么办，这就有了接下来的线性表的链式存储结构

2、单链表在内存的存储位置不一定是一段连续的位置，它可以存放在内存中任何地方

3、单链表中除了用于存放数据的数据域外，还有存放指针的指针域，指针域的作用是指向链表的下一个节点(因为链表的元素在内存中的存放时任意位置的，所以需要指向下一个节点)

4、单链表第一个节点存储的位置叫做头指针，整个单链表的存取都是从头指针开始，单链表的最后一个节点是指针指向空(NULL)

 

单链表的操作：

1 package com.alibaba.test03;
2
3 import org.junit.jupiter.api.Test;
4
5
6 /**
7
* 1.
单链表的具体实现及操作
8
* @author wydream
9
*
10
*/
11
12 public class SingLeLinkedList {
13
14
private int size;//链表节点的个数
15
private Node head;//头结点
16
17
public SingLeLinkedList() {
18
size=0;
19
head=null;
20
}
21
22
//链表中的每个节点类
23
private class Node{
24
private Object data;//每个节点的数据
25
private Node next;//每个节点指向下一个节点的连接
26
27
public Node(Object data){
28
this.data=data;
29
}
30
}
31
32
//在表头添加元素
33
public Object addHead(Object obj) {
34
Node newHead=new Node(obj);
35
36
if(size==0) {
37
head=newHead;
38
}else {
39
newHead.next=head;
40
head=newHead;
41
}
42
size++;
43
return obj;
44
}
45
46
//在链表头删除元素
47
public Object deleteHead() {
48
Object obj=head.data;
49
head=head.next;
50
size--;
51
return obj;
52
}
53
54
//查找指定元素，找到了返回元素Node，找不到返回Null
55
public Node find(Object obj) {
56
Node current=head;
57
int tempSize=size;
58
while(tempSize>0) {
59
if(obj.equals(current.data)) {
60
return current;
61
}else {
62
current=current.next;
63
}
64
tempSize--;
65
}
66
return null;
67
}
68
69
70
//删除指定的元素，删除成功则返回true
71
public boolean delete(Object value) {
72
73
if(size==0) {
74
return false;
75
}
76
77
Node current=head;
78
Node previous=head;
79
while(current.data!=value) {
80
if(current.next==null) {
81
return false;
82
}else {
83
previous=current;
84
current=current.next;
85
}
86
}
87
88
//如果删除的是第一个节点
89
if(current==head) {
90
head=current.next;
91
size--;
92
}else {//删除的不是第一个节点
93
previous.next=current.next;
94
size--;
95
}
96
return true;
97
}
98
99
//判断链表是否为空
100
public boolean isEmpty() {
101
return size==0;
102
}
103
104
//显示节点信息
105
public void display() {
106
if(size>0) {
107
Node node=head;
108
int tempSize=size;
109
if(tempSize==1) {//当前链表只有一个节点
110
System.out.println("["+node.data+"]");
111
return;
112
}
113
while(tempSize>0) {
114
if(node.equals(head)) {
115
System.out.print("["+node.data+"->");
116
}else if(node.next==null){
117
System.out.print(node.data+"]");
118
}else {
119
System.out.print(node.data+"->");
120
}
121
node=node.next;
122
tempSize--;
123
}
124
System.out.println();
125
}else {//如果链表一个节点都没有，直接打印
126
System.out.print("[]");
127
}
128
}
129
130
@Test
131
public void test() {
132
SingLeLinkedList s=new SingLeLinkedList();
133
s.addHead("1");
134
s.addHead("2");
135
s.addHead("3");
136
s.addHead("4");
137
s.deleteHead();
138
s.display();
139
}
140
141
142
143
144 }

有序链表：

概念：

• 前面的链表实现插入数据都是无序的，在有些应用中需要链表中的数据有序，这称为有序链表。
• 在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度(因为元素不需要移动)，另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。

有序链表的实现：

 1 /**
2
*
3
* @author wydream
4
*
5
*/
6
7 public class OrderLinkedList {
8
9
private Node head;
10
11
private class Node{
12
private int data;
13
private Node next;
14
15
public Node(int data) {
16
this.data=data;
17
}
18
}
19
20
public OrderLinkedList() {
21
head=null;
22
}
23
24
//插入节点，并按从小到大的顺序排列
25
public void insert(int value) {
26
Node node=new Node(value);
27
Node pre=null;
28
Node current=head;
29
while(current!=null&&value>current.data) {
30
pre=current;
31
current=current.next;
32
}
33
if(pre==null) {
34
head=node;
35
head.next=current;
36
}else {
37
pre.next=node;
38
node.next=current;
39
}
40
}
41
42
//删除头节点
43
public void deleteHead() {
44
head=head.next;
45
}
46
47
public void display() {
48
Node current=head;
49
while(current!=null) {
50
System.out.println(current.data+" ");
51
current=current.next;
52
}
53
System.out.println("");
54
}
55
56
57
58 }

双向链表： 

概念：

我们知道单向链表只能从一个方向遍历，那么双向链表它可以从两个方向遍历。

双向链表的实现：

1 import org.junit.jupiter.api.Test;
2
3 /**
4
*
双向链表的实现
5
* @author wydream
6
*
7
*/
8
9 public class TwoWayLinkedList {
10
11
private Node head;//链表头
12
private Node tail;//链表尾
13
private int size;//链表长度
14
15
16
private class Node{
17
private Object data;
18
private Node next;
19
private Node prev;
20
21
public Node(Object obj){
22
this.data=obj;
23
}
24
25
}
26
27
public TwoWayLinkedList(){
28
size=0;
29
head=null;
30
tail=null;
31
}
32
33
//在表头添加新节点
34
public void addHead(Object obj) {
35
Node node=new Node(obj);
36
//如果链表长度为零，则添加的这个元素就是头节点和尾节点
37
if(size==0) {
38
head=node;
39
tail=node;
40
}else {
41
head.prev=node;
42
node.next=head;
43
head=node;
44
}
45
46
size++;
47
}
48
49
//在链表尾添加新节点
50
public void addEnd(Object obj) {
51
Node newNode=new Node(obj);
52
if(size==0) {
53
head=newNode;
54
tail=newNode;
55
}else {
56
tail.next=newNode;
57
newNode.prev=tail;
58
tail=newNode;
59
}
60
size++;
61
}
62
63
//删除链表头
64
public Node deleteHead() {
65
Node temp=head;
66
if(size!=0) {
67
head=head.next;
68
head.prev=null;
69
size--;
70
}
71
return temp;
72
}
73
74
75
//删除链表尾
76
public void deleteEnd() {
77
Node end=tail;
78
if(size!=0) {
79
tail=tail.prev;
80
tail.next=null;
81
size--;
82
}
83
}
84
85
86
//获取链表节点个数
87
public int getLength() {
88
return size;
89
}
90
91
//判断链表是否为空
92
public boolean isEmpty() {
93
if(size>0) {
94
return true;
95
}
96
return false;
97
}
98
99
//显示节点信息
100
public void display() {
101
if(size>0) {
102
Node node=head;
103
int tempSize=size;
104
if(tempSize==1) {
105
System.out.println("["+node.data+"]");
106
return;
107
}
108
while(tempSize>0) {
109
if(node.equals(head)) {
110
System.out.print("["+node.data+"->");
111
}else if(node.equals(tail)) {
112
System.out.print(node.data+"]");
113
}else {
114
System.out.print(node.data+"->");
115
}
116
node=node.next;
117
tempSize--;
118
}
119
System.out.println();
120
}else {
121
System.out.println("[]");
122
}
123
124
}
125
126
@Test
127
public void test() {
128
TwoWayLinkedList tl=new TwoWayLinkedList();
129
tl.addEnd("1");
130
tl.addEnd("2");
131
tl.addEnd("3");
132
tl.addEnd("4");
133
tl.deleteHead();
134
tl.deleteEnd();
135
tl.display();
136
}
137
138
139 }