当前位置：网站首页 > 区块链基础 > 正文

算法通关村第一关——链表青铜挑战笔记

区块链基础 来源： 网络 编辑：小编 更新时间：2024-11-26 22:54:04 浏览量：16

1.单链表的概念

1.1 什么是链表

链表是一种常见的数据结构，用于在内存中存储和组织数据。它由一系列称为节点的元素组成，每个节点存储着数据以及指向下一个节点的引用。

链表中的节点可以在内存中的任何位置分布，它们不需要连续的内存空间。每个节点都包含两个部分：数据和指向下一个节点的指针或引用。这种指针使得链表中的节点能够按任意顺序连接在一起。

链表

链表常见的类型有单向链表和双向链表。在单向链表中，每个节点只有一个指向下一个节点的指针。而在双向链表中，每个节点既有一个指向下一个节点的指针，又有一个指向前一个节点的指针，这样可以更方便地进行双向遍历。

链表相对于数组拥有更好的插入和删除操作性能，因为它们不需要移动其他元素来腾出空间。但是链表的缺点是访问节点时需要顺序遍历，无法像数组那样通过索引直接访问元素。

总之，链表是一种常见的数据结构，可用于解决许多问题，比如实现栈、队列和图等其他数据结构，或者用于处理大型数据集合。

1.2 链表的相关概念

节点和头节点
在链表中，每一个点都是由值和指向下一个节点的地址组成的独立的单元，称为一个节点，有时也称节点，
对于单链表，如果知道了第一个元素，就可以通过遍历访问整个链表，因此第一个节点是最重要的，一般称为头节点。

虚拟节点
在工程项目中会经常看到虚拟节点的概念，其实就是一个节点dummpyNode，其next指针指向head，也就是dummpyNode.next=head。
因此，如果我们在算法中使用了虚拟节点，则要注意如果获得head节点，或者从方法（函数）里返回的时候，应该使用dummpyNode.next。
另外注意，dummpyNode的val不会被使用，初始化为0或-1都可以，既然不会使用，那虚拟节点拿来干啥呢？简单来说，就是为了方便我们处理首部节点，否则我们需要在代码里单独处理首部节点的问题。在链表反转里，我们会看到该方法可大大降低操作难度。

2. 如何构造单链表

我们来看如何构造单链表。

2.1 定义数据结构

2.1.1 C_版

链表的基本单位是节点，在C/C++的思想中，每个节点元素都配有一个指针，这意味着，链表上的每个"元素"都长下图这个样子：
图片描述
数据域用来存储元素的值，指针域用来存放指针，指向下一个元素的地址。数据结构中，通常将上图这样的整体称为节点。
也就是说，链表中实际存放的是一个一个节点，数据元素存放在各个节点的数据域中。举个简单的例子，下图中{1, 2, 3}的存储状态用链表表示，如下图所示：
在这里插入图片描述
至此，我们便可以给出清晰的C语言的链表定义：

// C语言版 struct ListNode { 
    int val; // 数据域，代表数据 ListNode* next; // 指针域，代表指针，直接指向后继元素 };

注意，采用结构体的话可能会对封装性有一定影响，不过为了后续调用成员方便，就暂时采取这样的方式。

2.1.2 Java/Python_版

先看java，首先我们要理解JVM（java虚拟机）是怎么构建出链表的，我们知道JVM里有栈区和堆区，栈区主要存引用，也就是一个指向实际对象的地址，而堆区存的才是创建的对象。
在java配套代码中BasicLink类，我们debug一下看一下从head开始next会发现是这样的：
在这里插入图片描述
这就是一个简单的线性访问了，所以链表就是从head开始，逐个开始向后访问，而每次所访问的对象的类型都是一样的。
类似的，根据面向对象理论，在java里规范的链表应该这么定义：

// java版 public class ListNode { 
    private int val; private ListNode next; public ListNode(int val) { 
    this.val = val; // 这个一般作用不大，写了会更加规范 this.next = null; } }

python类与java类具有相似的结构，不同的是，python中我采取了一个新的措施，先定义Node，再定义ListNode，其中__init__方法用于初始化对象，属性则用self.data，self.next的语法（public的访问权限）和self._head（private的访问权限）进行访问和设置，同样的，采用这样的方式实际上是缺失了一定的封装性，不过为了是后续方便罢了。

"""Python版""" class Node: def __init__(self, item): # item储存数据 self.item = item # next是下一个节点的标识 self.next = None class ListNode: """单链表""" def __init__(self): self._head = None

以上便是三种语言版的单链表定义，定义完链表的数据结构之后，我们开始来创建一个值为 [0， 1， 2， 3， 4]的链表：

2.2 创建单链表

2.2.1 C_版

首先是C语言版，核心算法是创建一个头节点，并将元素依次插到该节点后，形成一个带有头节点的单链表，并返回头节点，代码如下：

// 创建一个值为0 1 2 3 4 的链表 ListNode* initLink() { 
    ListNode* p = NULL; // 设置头指针 ListNode* temp = (ListNode*)malloc(sizeof(ListNode)); // 设置头节点 temp->val = 0; temp->next = NULL; p = temp; // 让头指针指向头节点(头指针就此固定) int i; for(i = 1; i < 5; i++){ 
    ListNode* a = (ListNode*)malloc(sizeof(ListNode)); // 每次创建一个临时的节点地址 a->val = i; a->next = NULL; temp->next = a; // 每次temp的指向的后继点就是临时节点a temp = temp->next; // temp又指向下一个节点(原本temp的后继点，也就是a)，为下一次添加节点做准备 } return p; }
2.2.2 Java_版

然后是java版，其算法思想和C一致（由于C的struct没有构造器，所以篇幅更长一点，但是核心思想相同）代码如下：

// 创建一个0, 1 ,2 ,3 ,4 的链表 public static ListNode initLink() { 
    ListNode head = new ListNode(0); // 先确定头节点 ListNode tem = head; for(int i = 1; i < 5; i++) { 
    ListNode node = new ListNode(i); tem.next = node; tem = node; } return head; }
2.2.3 Python_版

至于Python版，由于数据结构与前面二者有所区别，所以创建列表时的算法思想也不太相同，先定义插入头部尾部元素的函数，再进行构建，代码如下：

 def add(self, item): """头部添加元素""" # 先创建一个保存item的节点 node = Node(item) # 将新节点的连接域next指向头节点 node.next = self._head # 将链表的头_head指向新节点 self._head = node def append(self, item): """尾部添加元素""" node = Node(item) # 先判断链表是否为空，若为空链表，则将_head指向新节点 if self.is_empty(): self._head = node # 若不为空，则找到尾部，将尾节点的next指向新节点 else: cur = self._head while cur.next is not None: cur = cur.next cur.next = node # 创建一个0, 1 ,2 ,3 ,4 的链表 def initLink(self): for i in range(5): self.append(i)

以上便完成了单链表的构建，接下来进入增删改查环节。

3. 单链表的增删改查

由于算法的核心思想是互通的，所以统一介绍完思想后直接提供三个版本的代码。

3.1 遍历链表

对于单链表，不管进行什么操作，一定是从头开始逐个向后访问，所以操作之后是否还能找到表头就显得尤为重要，为避免弄丢表头，需要创建一个临时变量来遍历链表。
在这里插入图片描述
代码如下：

3.1.1 C_版
// 打印链表 void printList(ListNode* p) { 
    ListNode* temp = p; // 避免弄丢头节点的位置，创建一个临时节点指针temp用来遍历链表 while(temp) { 
    // 当temp指向末尾(null)时，终止循环 printf("%d ", temp->val); // 打印数据 temp = temp->next; // 指向下一个节点 } printf("\n"); } // 获取链表长度 int32_t getLength(ListNode* p) { 
    int Length = 0; // 初始化长度为0 ListNode* temp = p; // 避免弄丢头节点的位置，创建一个临时节点指针temp用来遍历链表 while(temp) { 
    // 当temp指向末尾(null)时，终止循环 Length++; // 打印数据 temp = temp->next; // 指向下一个节点 } return Length; }

测试方法：

int main(){ 
    // 测试 printLis 和 getLength ListNode* p = NULL; p = initLink(); // 创建链表 printf(" The list is :"); printList(p); // 测试输出 int length = getLength(p); // 测试长度 printf(" The length of list is : %d", length); printf("\n"); return 0; }
3.1.2 Java_版
// 获取链表长度 public static int getListLength(ListNode head) { 
    int length = 0; ListNode node = head; // 为避免弄丢表头，创建一个临时变量来操控 while(node != null) { 
    length++; node = node.next; } return length; } // 打印链表 public static void printList(ListNode head) { 
    ListNode node = head; // 为避免弄丢表头，创建一个临时变量来操控 while(node != null) { 
    System.out.print(" " + node.val); node = node.next; } System.out.println(); }

测试方法：

class useListNode{ 
    // 为了体现封装性，在另一个类中调用函数 public static void main(String[] args){ 
    // 由于ListNode中每一个函数都是static，所以可以使用静态方法调用 System.out.println("初始化列表为: "); ListNode head = ListNode.initLink(); ListNode.printList(head); System.out.println("列表的长度为: " + ListNode.getListLength(head)); } }
3.1.3 Python_版
 def length(self): """链表长度""" # cur初始时指向头节点 cur = self._head count = 0 # 尾节点指向None, 当未达到尾部时 while cur is not None: count += 1 # 将cur后移一个节点 cur = cur.next return count def travel_print(self): """遍历链表""" cur = self._head while cur is not None: print(cur.item, end=" ") cur = cur.next print("")

测试方法：

# 初始化 list = ListNode() list.initLink() # 打印 print("List :", end=' ') list.travel_print() # 长度 print("The length of list is: " + str(list.length()))

3.2 链表插入

单链表的插入，需要考虑三种情况：首部，中部，尾部。

（1）在链表的表头插入

链表表头插入新结点非常简单，容易出错的是经常会忘了head需要重新指向表头。需要创建一个新结点newNode，怎么连接到原来的链表上呢？执行newNode.next-head即可。之后要遍历新链表就要从newNode开始一路next向下，最后让head=newNode就行了，如下图：
list6
（2）在链表中间插入

在中间位置插入，必须先遍历找到要插入的位置，然后将当前位置接入到前驱结点和后继结点之间，但是到了该位置之后却不能获得前驱结点了，也就无法将结点接入进来了。这就好比一边过
河一边拆桥，结果自己也回不去了。
为此，我们要在目标结点的前一个位置停下来，也就是使用cur.next的值而不是cur的值来判断，这是链表最常用的策略。
例如下图中，如果要在7的前面插入，当curnext=node(7)了就应该停下来，此时cur.val=15。然后需要给newNode前后接两根线，此时只能先让new.next=node(15).next(图中虛线)，然后node(15).next=new，而且顺序不能错。
想一下为什么不能颠倒顺序？
由于每个节点都只有一个next，因此执行了node(15).next=new之后，结点15和7之间的连线就自动断升了，如下图所示：
list7
（3）在单链表的结尾插入

在表尾插入比较容易，只需将尾节点指向新节点即可。
list8
代码如下：

3.2.1 C_版
// 插入节点 ListNode* insertNode(ListNode* head, ListNode* nodeInsert, int position) { 
    if(head == NULL) { 
    // 如果头节点是空的，那么待插入的节点就是头节点或者抛出一个异常 return nodeInsert; } // 判断待插入的长度是否合理 int size = getLength(head); if (position > size + 1 || position < 1) { 
    printf("待插入的位置有误\n"); // 抛出异常 return head; } // 插入节点到头部 if (position == 1){ 
    nodeInsert->next = head; head = nodeInsert; return head; } // 插入节点到中间和尾部 ListNode* pNode = head; int count = 1; while(count < position - 1) { 
    // 找到待插入的位置的前驱节点 pNode = pNode->next; count++; } nodeInsert->next = pNode->next; pNode->next = nodeInsert; return head; }

测试函数：

// 测试插入节点的函数 void testInsert() { 
    ListNode* head = NULL; // 插入头部的节点 ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->val = 1; node->next = NULL; head = insertNode(head, node, 1); printList(head); // 插入尾部的节点 node = (ListNode*)malloc(sizeof(ListNode)); node->val = 3; node->next = NULL; head = insertNode(head, node, 2); printList(head); // 插入中间的节点 node = (ListNode*)malloc(sizeof(ListNode)); node->val = 2; node->next = NULL; head = insertNode(head, node, 2); printList(head); }
3.2.2 Java_版
// 插入节点 public static ListNode insertNode(ListNode head, ListNode nodeInsert, int position) { 
    if(head == null) { 
    return nodeInsert; // 如果头节点为空，则待插入的节点表示头节点，也可以抛出一个异常 } int size = getListLength(head); if (position < 1 || position > size + 1) { 
    System.out.println("位置参数越界"); return head; } if(position == 1) { 
    // 表头插入 nodeInsert.next = head; head = nodeInsert; return head; } ListNode pNode = head; // 中间插入和尾部插入 int count = 1; while(count < position - 1) { 
    pNode = pNode.next; count++; } nodeInsert.next = pNode.next; pNode.next = nodeInsert; return head; }

测试函数：

public static void textInsert() { 
    ListNode head = null; ListNode node = new ListNode(1); head = insertNode(head, node, 1); // 表头插入 printList(head); node = new ListNode(3); head = insertNode(head, node, 2); // 尾部插入 printList(head); node = new ListNode(2); insertNode(head, node, 2); // 中间插入 printList(head); }
3.2.3 Python_版
 # 指定位置插入节点 def insert(self, pos, item): """指定位置添加元素""" # 若指定位置pos为第一个元素之前，则执行头部插入 if pos <= 0: self.add(item) # 若指定位置pos超过链表尾部，则执行尾部插入 elif pos > (self.length() - 1): self.append(item) # 找到指定位置 else: node = ListNode(item) count = 0 # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置 pre = self._head while count < (pos - 1): count += 1 pre = pre.next # 先将新节点node的next指向插入位置的节点 node.next = pre.next # 将插入位置的前一个节点的next指向新节点 pre.next = node

3.3 链表删除

删除同样分为删除头部元素，删除中间元素和删除尾部元素。

（1）删除表头节点

删除表头元素还是比较简单的，一般只要执行head=head->next就行。如下图，将head向前移动一次后，原来的节点不可达，然后就可以将其删除。
image10
（2）删除尾部节点

删除的过程不算复杂，也是找到要删除的节点的前驱节点，这里同样要在提前一个位置判断，例如下图中删除40，其前驱节点为7。遍历的时候需要判断cur->next是否为40，如果是，则只需执行cur-next = null 即可，此时节点40就可以放心删掉了。
image11
（3）删除中间节点

删除中间节点时，也会用cur.next来比较，找到位置后，将cur->next指针的值更新为cur->next->next，然后就可以放心的将node(6)删掉了。
image12
代码如下：

3.3.1 C_版
// 删除节点 ListNode* deleteNode(ListNode* head, int position) { 
    if(head == NULL) { 
    return NULL; } int size = getLength(head); if(position > size || position < 1) { 
    printf("输入范围有误\n"); return head; } if(position == 1) { 
    // 删除头节点 ListNode* cur = head; head = head->next; free(cur); return head; } else { 
    // 删除中间节点或尾节点 ListNode* cur = head; int count = 1; while(count < position - 1) { 
    // 找到待插入的位置的前驱节点 cur = cur->next; count++; } ListNode* tem = cur->next; cur->next = tem->next; free(tem); return head; } }

测试函数：

// 删除节点的测试函数 void testDelete() { 
    // 创建0~4的列表 ListNode* p = NULL; p = initLink(); printList(p); // 删除第一个元素 p = deleteNode(p, 1); printList(p); // 删除中间元素 p = deleteNode(p, 2); printList(p); // 删除最后一个元素 p = deleteNode(p, getLength(p)); printList(p); }
3.3.2 Java_版
// 删除节点 public static ListNode deleteNode(ListNode head, int position) { 
    if(head == null) { 
    return null; } int size = getListLength(head); if(position < 1 || position > size) { 
    System.out.println("输入参数有误"); return head; } if(position == 1) { 
    return head.next; }else { 
    ListNode cur = head; int count = 1; while(count < position - 1) { 
    cur = cur.next; count++; } ListNode curNode = cur.next; cur.next = curNode.next; // 上面两行代码可以简化为 cur.next = cur.next.next; } return head; }

测试函数：

public static void textDelete() { 
    ListNode head = initLink(); printList(head); // 删除第一个元素 head = deleteNode(head, 1); printList(head); // 删除中间的元素 head = deleteNode(head, 2); printList(head); // 删除最后一个元素 head = deleteNode(head, getListLength(head)); printList(head); }
3.3.3 Python_版
 # 删除节点 def remove(self, item): """删除节点""" cur = self._head pre = None while cur is not None: # 找到指定元素 if cur.item == item: # 如果第一个就是删除的节点 if not pre: # 将头指针指向头节点的后一个节点 self._head = cur.next else: # 将删除位置前一个节点的next指向删除位置的后一个节点 pre.next = cur.next break else: # 按照链表后移节点 pre = cur cur = cur.next

在很多算法中链表元素是有序的，此时如果要插入或删除某个元素，则要先遍历链表，找到目标元素后再做插入和删除。

到此这篇算法通关村第一关——链表青铜挑战笔记的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！

  • 上一篇： 什么是BT种子、迅雷下载链接、磁力链接
  • 下一篇： 作用域和作用域链

    • 版权声明：

    本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
    如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！


    转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/10371.html

    # —— # 笔记

    相关文章：

  • 什么是BT种子、迅雷下载链接、磁力链接2024-11-26 22:54:04
  • 推荐一个bilibili视频链接解析网站2024-11-26 22:54:04
  • 《区块链基础知识25讲》-各讲地址整理_区块链的地址2024-11-26 22:54:04
  • 区块链基础架构_区块链系统架构2024-11-26 22:54:04
  • 区块链基础知识2024-11-26 22:54:04
  • 作用域和作用域链2024-11-26 22:54:04
  • 单向链表和双向链表区别（单链表和双向链表的区别）2024-11-26 22:54:04
  • 单向链表（单向链表和双向链表区别）2024-11-26 22:54:04
  • 如何点击图片跳转链接（点击图片跳转链接软件叫什么）2024-11-26 22:54:04
  • 跳转链接怎么制作ppt（ppt如何做跳转链接）2024-11-26 22:54:04
    • ❮ 全屏图片 ❯