数据结构和算法之链表（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; //将头指针赋值给currentNode 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); } }
