《算法导论》学习笔记之Chapter10---数据结构之链表

本文主要是介绍《算法导论》学习笔记之Chapter10---数据结构之链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链表定义：链表是这样一种数据结构，其中的各对象按线性顺序排列，与数组的线性顺序由下标决定不同，链表的顺序是由各个对象里的指针决定。

链表分为：单向链表，双向链表，还有循环链表。

链表支持的操作有：查找Search；插入Insert；删除Delete；

双向链表的查找操作就是从表头开始对比查找，很简单；插入操作，是根据插入的数据的指针属性来寻找要插入的位置；之后修改相关元素的pre和next指针属性即可；删除操作与插入操作类似，只是在找到要删除的元素的位置之后，直接将该元素前一个节点的next属性设置为被删除节点的next属性值，将被删除节点后面的节点的pre属性值设置为被删除节点的pre属性值即可。可以自行画图来加深理解。而在链表中，有一个重要的定义就是-节点，前面所说的元素值，pre,next属性都应该包含在节点里面的。

注意，链表的查找，删除操作其实都是可以分为按照内容的操作和按照指针的操作的。

本文，介绍单向链表和双向链表的几种java实现。

下面是单向链表的基本操作的代码实现：

import java.util.List;public class LinkedListTest {Node head = null;// 链表头/*** 向链表中插入数据* * @param args*/public void insert(int d) {Node newNode = new Node(d);// 将要插入的数据包装成链表的节点// 如果链表为空，则将要插入节点作为头节点if (head == null) {head = newNode;return;}// 下面代码是寻找链表的尾节点Node tmp = head;while (tmp.next != null) {tmp = tmp.next;}// 将新节点插入大奥为节点的后面tmp.next = newNode;}// 删除第i个节点public boolean deletaNode(int i) {// 如果删除的位置不合理，则返回falseif (i < 1 && i > length()) {return false;}// 删除的是链表的头结点if (i == 1) {head = head.next;return true;}// 删除的是链表的中间节点int j = 2;Node preNode = head;Node curNode = preNode.next;while (curNode != null) {if (j == i) {preNode.next = curNode.next;return true;}preNode = curNode;curNode = curNode.next;j++;}return true;}// 返回链表的长度public int length() {int length = 0;Node tmp = head;while (tmp != null) {tmp = tmp.next;length++;}return length;}// 链表排序,返回排序后的头节点public Node sortList() {Node nextNode = null;int tmp = 0;Node curNode = head;// 采用冒泡排序的方法对链表数据进行排序while (curNode.next != null) {nextNode = curNode.next;while (nextNode != null) {if (curNode.data > nextNode.data) {tmp = curNode.data;curNode.data = nextNode.data;nextNode.data = tmp;}nextNode = nextNode.next;}curNode = curNode.next;}return head;}// 打印链表public void printList() {Node tmp = head;while (tmp != null) {System.out.println(tmp.data);tmp = tmp.next;}}public static void main(String[] args) {// TODO Auto-generated method stubLinkedListTest list = new LinkedListTest();list.insert(5);list.insert(1);list.insert(4);list.insert(3);list.insert(2);System.out.println(list.length());list.printList();list.sortList();list.printList();list.deletaNode(1);list.printList();list.deletaNode(3);list.printList();}}// 定义链表的节点类型
class Node {int data;Node next = null;public Node(int data) {this.data = data;}
}

下面介绍单链表中的删除重复数据的方法：

/*** 删除重复数据 方法1时间复杂度小，但是需要额外的存储空间 方法2时间复杂度高，但是不需要额外的存储空间* * @param head*/public void deleteDuplecate1(Node head) {Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();Node tmp = head;Node pre = null;while (tmp != null) {if (table.containsKey(tmp.data)) {pre.next = tmp.next;} else {table.put(tmp.data, 1);pre = tmp;}tmp = tmp.next;}}public void deleteDuplecate2(Node head) {Node tmp = head;while (tmp != null) {Node cur = head;Node pre = null;while (cur != tmp) {if (cur.data == tmp.data) {pre.next = cur.next;break;} else {pre = cur;cur = cur.next;}}tmp = tmp.next;}tmp = tmp.next;}

寻找链表中倒数第k个节点：

//如何找到链表中倒数第k个节点，重点在倒数public Node find(Node head, int k){if( k < 1 || k > this.length()){return null;}Node p1 = head;Node p2 = head;//将p1指针向后先移动k个位置，这样当P1移动到结尾时，p2的位置就是倒数第kfor(int i = 0; i < k - 1; i++){p1 = p1.next;}while(p1 != null){p1 = p1.next;p2 = p2.next;}return p2;}

实现链表的反转（非递归实现）：

// 链表反转非递归实现public void reverse(Node head) {Node pRevereHead = head;Node pNode = head;Node pPre = null;while (pNode != null) {// pNext用来记录下一个节点，防止pNode的next节点转向之后，与后面的节点断开联系Node pNext = pNode.next;if (pNext == null) {pRevereHead = pNode;}pNode.next = pPre;pPre = pNode;pNode = pNext;}this.head = pRevereHead;}

下面还有关于单向链表的好几种操作，在此我就只记录一下这几个操作的思想吧：

从链表尾部开始输出节点：使用递归，每访问到一个节点，先递归输出后面的节点，再输出该节点自身。

访问链表中间节点：是用两个指针，一个指针单步移动，一个指针双步移动，当双步指针移动到链表尾部，则单步指针指向的节点为链表中间节点。

如何判断两个链表是否相交：如果链表相交，则一定有相同的尾节点。

这篇关于《算法导论》学习笔记之Chapter10---数据结构之链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---