数据结构和算法之链表（Java语言实现）
一、什么是链表
链表是一种用于存储数据集合的数据结构。链表具有以下属性
相邻元素之间通过指针连接最后一个元素的后继指针为NULL在程序执行过程中，链表的长度可以增加或者减小链表的空间能够按需分配（直到系统内存耗尽）没有内存空间的浪费（但是链表中的指针需要一些额外的内存开销）
二、链表抽象数据类型
2.1、链表的主要操作
插入：插入一个元素到链表中删除：移出并返回链表中指定元素的位置
2.2、链表的辅助操作
删除链表：移出链表中的所有元素计数：返回链表中元素的个数查找：寻找从链表表尾开始的第n个结点
三、单向链表
我们口中常说的链表一般默认为单向链表，它包含多个结点，每个结点有一个指向后继元素的next（下一个）指针。链表中最后一个结点的next指针值为NULL，表示该链表的结束
下面展示一个链表的基本声明
public class ListNode {
private int data
;
private ListNode next
;
public int getData() {
return data
;
}
public ListNode
getNext() {
return next
;
}
public void setData(int data
) {
this.data
= data
;
}
public void setNext(ListNode next
) {
this.next
= next
;
}
}
3.1、链表的基本操作
遍历链表
遍历链表需完成以下步骤
沿指针遍历
遍历时显示结点的内容
当next指针的值为NULL时遍历结束
int listLength(ListNode head
) {
int length
= 0;
ListNode currentNode
= head
;
while (currentNode
!= null
){
length
++;
currentNode
= currentNode
.getNext();
}
return length
;
}
从链表中插入一个元素
单向链表的插入操作可以分为以下三种情况
在链表的表头插入一个新结点
先将要插入的结点的next指针指向当前的表头结点
然后更新表头指针的值，使其指向新结点
在链表的表尾插入一个新结点
先将要插入的结点的next指针指向NULL
然后将要当前链表的最后一个结点的next指针指向新结点
在链表的中间位置插入一个新结点
假设给点插入新结点的位置。在这种情况下，需要修改两个位置的指针
如果想要在位置4增加一个元素，则需要将指针定位于链表的位置3。假设第4个结点为位置节点，新结点的next指针指向位置结点
然后将第3个位置的next指针指向新结点
ListNode
insertInLikeList(ListNode head
,ListNode nodeInsert
,int position
){
if (head
== null
){
return nodeInsert
;
}
int size
= listLength(head
);
if (size
> position
+ 1 || position
< 1){
System
.out
.println("Position of node to insert is invalid. the valid inputs are 1 to " + (position
+ 1));
return head
;
}
if (position
== 1){
nodeInsert
.setNext(head
);
return nodeInsert
;
}else {
ListNode previousNode
= head
;
int count
= 1;
while (count
< position
- 1){
previousNode
= previousNode
.getNext();
count
++;
}
ListNode currentNode
= previousNode
.getNext();
nodeInsert
.setNext(currentNode
);
previousNode
.setNext(nodeInsert
);
}
return head
;
}
从链表中删除一个元素
同样的，在链表中删除一个元素也同样会有三种情况出现
删除头结点
1、创建一个临时结点，让它指向表头指针指向的结点
2、修改表头指针的结点，使其指向下一个结点，并移除临时结点
删除中间位置的一个元素
删除链表的最后一个结点
ListNode
deleteNodeFormLikeList(ListNode head
,int position
){
int size
= listLength(head
);
if (position
> size
|| position
< 0){
System
.out
.println("Position of node delete is invalid. the valid inputs are 1 to" + size
);
return head
;
}
if (position
== 1){
ListNode currentNode
= head
.getNext();
head
= null
;
return currentNode
;
}else {
ListNode previousNode
= head
;
int count
= 1;
while (count
< position
){
previousNode
= previousNode
.getNext();
count
++;
}
ListNode currentNode
= previousNode
.getNext();
previousNode
.setNext(currentNode
.getNext());
currentNode
= null
;
}
return head
;
}
删除单向链表
void deleteLinkList(ListNode head
){
ListNode auxiliary
,iterator
= head
;
while (iterator
!= null
){
auxiliary
= iterator
.getNext();
iterator
= null
;
iterator
= auxiliary
;
}
}
最后附上测试的完整代码
public class ListNode {
private int data;
private ListNode next;
public ListNode(int data){
this.data = data;
}
public int getData() {
return data;
}
public ListNode getNext() {
return next;
}
public void setData(int data) {
this.data = data;
}
public void setNext(ListNode next) {
this.next = next;
}
/**
*遍历链表
*
*/
int listLength(ListNode head) {
int length = 0;
ListNode currentNode = head;
while (currentNode != null){
length++;
currentNode = currentNode.getNext();
}
return length;
}
/**
* 向链表中插入一个元素
*/
ListNode insertInLikeList(ListNode head,ListNode nodeInsert,int position){
if (head == null){
//如果链表为空，直接插入
return nodeInsert;
}
int size = listLength(head);
//先判断插入的位置是否合法
if (size > position + 1 || position < 1){
System.out.println("Position of node to insert is invalid. the valid inputs are 1 to " + (position + 1));
return head;
}
if (position == 1){
//如果在头部位置插入
nodeInsert.setNext(head);
return nodeInsert;
}else {
//在链表的中间位置或者尾部插入
ListNode previousNode = head;
int count = 1;
while (count < position - 1){
previousNode = previousNode.getNext();
count++;
}
ListNode currentNode = previousNode.getNext();
nodeInsert.setNext(currentNode);
previousNode.setNext(nodeInsert);
}
return head;
}
/**
* 删除链表中的一个元素
*/
ListNode deleteNodeFormLikeList(ListNode head,int position){
int size = listLength(head);
if (position > size || position < 0){
System.out.println("Position of node delete is invalid. the valid inputs are 1 to" + size);
return head;
}
if (position == 1){
ListNode currentNode = head.getNext();
head = null;
return currentNode;
}else {
ListNode previousNode = head;
int count = 1;
while (count < position ){
previousNode = previousNode.getNext();
count++;
}
ListNode currentNode = previousNode.getNext();
previousNode.setNext(currentNode.getNext());
currentNode = null;
}
return head;
}
/**
*删除整个链表
*/
void deleteLinkList(ListNode head){
ListNode auxiliary ,iterator = head;
while (iterator != null){
auxiliary = iterator.getNext();
iterator = null;
iterator = auxiliary;
}
}
public static void main(String[] args) {
ListNode Linklist = new ListNode(20);
ListNode head = new ListNode(30);
ListNode nodeInsert = new ListNode(3);
System.out.println(Linklist.listLength(head));
Linklist.setData(22);
Linklist.insertInLikeList(head,nodeInsert,2);
Linklist.setData(25);
System.out.println(Linklist.listLength(head));
for (int i = 1 ; i <= Linklist.listLength(head); i++){
Linklist.setData(i + 10);
System.out.println(Linklist.getData());
}
System.out.println("------------------------");
System.out.println(Linklist.getData());
Linklist.deleteNodeFormLikeList(head,1);
System.out.println("delete one number, the LinkList datas are " + Linklist.getData());
Linklist.deleteLinkList(head);
}
}
