【数据结构】单链表_单链表 博客

单链表是一种线性数据结构，每个元素都存放在链表的一个结点中，结点之间由指针串联在一起，这样就形成了一条如同链的结构，固称作链表。**所谓单链表顾名思义就是只能单方向遍历的链表。**如下图所示：

单链表的基本操作

单链表最基本的操作包括创建一个单链表、向单链表中插入结点、从单链表中删除结点等。

java版本的实现

package dataStructure;

class Node{
	int data;
	Node next = null;
	
	//创建节点
	public Node(int d) {
		data = d;
		next = null;
	}
}

public class SingleList {
	
	//单链表的头结点
	Node head;
	
	public SingleList() {
		head = null;
	}
	
	//计算单链表长度
	int ListLength() {
		int length = 0;
		Node currentNode = head;
		
		// 遍历单链表
		while(currentNode != null) {
			length++;
			currentNode = currentNode.next;
		}
		return length;
	}
	//打印单链表
	 void Print() {
		Node cur = head;
		if(cur == null ) {
			System.out.print("null");
		}
		while(cur != null) {
			System.out.print(cur.data+"->");
			cur = cur.next;		
		}
		System.out.println();
	}
	
	//单链表的插入
	Node Insert(Node node,int position) {
		
		if(head == null ) {	
			head = node;
			return head; 
		}
		
		int size = ListLength();
		if(position < 1 || position > size+1) {
			System.out.println("违法插入");
			return head;
		}
		
		if(position == 1) {
			node.next = head;
			head = node;
			return head;
		}else {
			int count = 1;
			Node it = head;
			//找到插入的位置的前一个结点
			while(count < position-1) {
				it = it.next;
				count++;		
			}
			node.next = it.next;
			it.next = node;
		}
		return head;
		
	}
	//删除单链表指定的结点
	Node deleteNode(int position) {
		Node it = head;
		int size = ListLength();
		
		if(position > size || position < 1) {
			System.out.println("违法删除");
			return head;
		}
		
		if(position == 1) {
			Node currentNode = head.next;
			head = currentNode;
			return currentNode;
		}else { 
			int count = 1;
			while(count < position-1) {
				it = it.next;
				count++;
			}
			it.next =it.next.next;
						
		}
		
		return head;
	}
	
	//删除整个单链表
	Node deleteSingList() {
		Node cur = head;
		Node rear = head;
		head = null;
		while(cur != null) {
			rear = cur.next;
			cur= null;
			cur = rear;
		}
		
		return head;
	}
	
	public static void main(String[] args) {
		SingleList list = new SingleList();
		
		list.Insert(new Node(1),2);
	    list.Insert(new Node(3),2);
	    list.Insert(new Node(2),2);
		list.Print();
	    list.deleteNode(1);
		list.Print();
		list.deleteSingList();
		list.Print();
	}
}



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