• 数据结构小记【Python/C++版】——链表篇


    一,基础概念

    链表是一种线性表结构,节点是链表中的基本单元。

    链表是节点的集合,节点可以分布在内存中的任何位置,每个节点都存储着链表中下一个节点的地址。

    如图,看似随意摆放的各个节点,其内部其实有链表维持的相对位置信息。

    我们用“指针”来表示链表中的方向,为了维持节点之间的先后顺序,链表给每个节点都附加了一个指针。单链表中的每个节点都包含指向后一个节点的后向指针,双链表中的每个节点不仅包含指向后一个节点的后向指针,也包含指向前一个节点的前向指针。链表在内存上不一定是连续分布的,我们只能沿着指针的方向迭代遍历链表上的节点,无法直接根据下标来访问链表指定位置上的元素。

    链表和数组相比,主要优势: 

    1.链表在编译期不需要知道具体大小。

    2.数组中的元素在内存中是连续分布的,且以相同距离间隔开。因此,往数组中插入新的元素就需要移动数组中的其他数据,链表不需要这么麻烦。

    数组的内存分布:

    链表的内存分布: 

    二,链表的图示结构

    不包含头节点和尾节点的链表:

    包含头节点和尾节点的链表:

    三,节点的代码表示 

    以单链表为例,节点的组成:

    1,数据域:节点的元素值

    2,指针域:指向下一个节点的指针

    Python实现:

    1. class Node:
    2. def __init__(self, value):
    3. self.data = value
    4. self.next = None

    C++实现:

    1. struct Node {
    2. int value; //节点的元素值,假设存储的元素是int类型
    3. Node *next; //后向指针
    4. Node(int val = 0) { value = val; next = NULL; } //构造函数
    5. };

    如果要实现双链表,且用泛型来表示元素值的类型,可以这样实现节点:

    1. template <typename T>
    2. struct Node {
    3. T value; //节点的元素值
    4. Node *next; //后向指针
    5. Node *prev; //前向指针
    6. Node() { next = NULL; prev = NULL; } //默认构造函数
    7. Node(const T &val) { value = val; next = NULL; prev = NULL; } //初始化元素值的构造函数
    8. };

    四,链表常见操作

    1.初始化和使用链表

    Python实现:

    1. class Node:
    2. def __init__(self, item):
    3. self.item = item
    4. self.next = None
    5. class LinkedList:
    6. def __init__(self):
    7. self.head = None
    8. if __name__ == '__main__':
    9. linkedList = LinkedList()
    10. linkedList.head = Node(1)
    11. second = Node(2)
    12. third = Node(3)
    13. #连接各个节点
    14. linkedList.head.next = second
    15. second.next = third
    16. while linkedList.head != None:
    17. print(linkedList.head.item, end=" ")
    18. linkedList.head = linkedList.head.next

    C++实现:

    1. #include
    2. using namespace std;
    3. class Node {
    4. public:
    5. int value;
    6. Node* next;
    7. };
    8. int main() {
    9. Node* head;
    10. Node* one = NULL;
    11. Node* two = NULL;
    12. Node* three = NULL;
    13. one = new Node();
    14. two = new Node();
    15. three = new Node();
    16. one->value = 1;
    17. two->value = 2;
    18. three->value = 3;
    19. //连接各个节点
    20. one->next = two;
    21. two->next = three;
    22. three->next = NULL;
    23. head = one;
    24. while (head != NULL) {
    25. cout << head->value << endl;
    26. head = head->next;
    27. }
    28. }

    2.链表往后追加节点

    Python实现:

    1. def append(self, new_element):
    2. current = self.head
    3. if self.head:
    4. while current.next:
    5. current = current.next
    6. current.next = new_element
    7. else:
    8. self.head = new_element

    C++实现:

    1. class Node
    2. {
    3. public:
    4. int data;
    5. Node* next;
    6. };
    7. void append(Node** head_ref, int new_data)
    8. {
    9. Node* new_node = new Node();
    10. Node* last = *head_ref;
    11. new_node->data = new_data;
    12. new_node->next = NULL;
    13. if (*head_ref == NULL)
    14. {
    15. *head_ref = new_node;
    16. return;
    17. }
    18. while (last->next != NULL)
    19. {
    20. last = last->next;
    21. }
    22. last->next = new_node;
    23. return;
    24. }

    3.链表指定位置添加节点

    Python实现:

    1. def insert(self, new_element, position):
    2. counter = 1
    3. current = self.head
    4. if position > 1:
    5. while current and counter < position:
    6. if counter == position - 1:
    7. new_element.next = current.next
    8. current.next = new_element
    9. current = current.next
    10. counter += 1
    11. elif position == 1 :
    12. new_element.next = self.head
    13. self.head = new_element

    C++实现:

    1. class Node
    2. {
    3. public:
    4. int data;
    5. Node *next;
    6. };
    7. void insert(Node* prev_node, int new_data)
    8. {
    9. if (prev_node == NULL) {
    10. cout << "The given previous node cannot be NULL";
    11. return;
    12. }
    13. Node* new_node = new Node();
    14. new_node->data = new_data;
    15. //最核心的两步
    16. new_node->next = prev_node->next;
    17. prev_node->next = new_node;
    18. }

    4.获得链表长度 

    Python实现:

    1. def getlength(self):
    2. current = self.head
    3. count = 0
    4. while current.next:
    5. count = count + 1
    6. current = current.next
    7. return count

    C++实现:

    1. int getlength(Node* head)
    2. {
    3. int count = 0;
    4. Node* current = head;
    5. while (current != NULL) {
    6. count++;
    7. current = current->next;
    8. }
    9. return count;
    10. }

    5.删除指定节点

    具体操作:   将前一个节点的next指针指向被删除节点的下一个节点

    Python实现: 

    示意图:

    1. def delete(self, value):
    2. current = self.head
    3. previous = None
    4. while current.value != value and current.next:
    5. previous = current
    6. current = current.next
    7. if current.value == value:
    8. if previous:
    9. previous.next = current.next
    10. else:
    11. self.head = current.next

    C++实现: 

    1. typedef struct Node {
    2. int data;
    3. struct Node* next;
    4. } Node;
    5. void delete(Node** head, int position)
    6. {
    7. Node* temp;
    8. Node* prev;
    9. temp = *head;
    10. prev = *head;
    11. for (int i = 0; i < position; i++) {
    12. if (i == 0 && position == 1) {
    13. *head = (*head)->next;
    14. free(temp);
    15. }
    16. else {
    17. if (i == position - 1 && temp) {
    18. prev->next = temp->next;
    19. free(temp);
    20. }
    21. else {
    22. prev = temp;
    23. if (prev == NULL)
    24. break;
    25. temp = temp->next;
    26. }
    27. }
    28. }
    29. }

    6.查询某节点是否存在

    Python实现:

    1. def search(self, item):
    2. current = self.head
    3. found = False
    4. while current != None and not found:
    5. if current.value == item:
    6. found = True
    7. else:
    8. current = current.next()
    9. return found

    C++实现:

    1. class Node {
    2. public:
    3. int data;
    4. Node* next;
    5. };
    6. bool search(Node* head, int x)
    7. {
    8. Node* current = head;
    9. while (current != NULL) {
    10. if (current->data == x)
    11. return true;
    12. current = current->next;
    13. }
    14. return false;
    15. }

    五,链表的主要使用场景

    如果应用场景包含很多查询操作,此时更适合使用数组。如果应用场景中,需要使用的元素个数不确定,且需要经常对元素进行添加和删除操作,此时使用链表结构会更合适。简单概括就是,链表适合使用在频繁增删的场景,数组适合使用在频繁查询的场景。

    六,参考阅读

    《Problem Solving with Algorithms and Data Structures Using Python, Second Edition》
    https://www.programiz.com/dsa/linked-list
    https://www.geeksforgeeks.org/what-is-linked-list/?ref=lbp
    https://gist.github.com/bavly/ef45e5b9db7d9a400b51ec132f553a0a
    https://pumpkinprogrammerdotcom4.wordpress.com/2014/06/13/c-tutorial-intro-to-linked-lists/
  • 相关阅读:
    解决合宙Esp32c3简约版不能Arduino ide开发的问题
    生成音频二维码:点燃听觉体验的魔法之门
    阿里云服务器的介绍和使用
    计算机网络(十)——其他重要协议
    docker 安装rabbitmq并配置hyperf使用
    在线预览编辑PDF::RAD PDF for ASP.NET
    聊聊spring的TransactionSynchronizationAdapter
    Android protobuf TextFormat、JsonFormat 序列化、反序列化
    北大联合智源提出训练框架LLaMA-Rider
    多亏这个面试,95后跳槽阿里网友晒工资条
  • 原文地址:https://blog.csdn.net/CoderZZ_2024/article/details/136521849