21xrx.com
2024-12-31 20:30:03 Tuesday
登录
文章检索 我的文章 写文章
带头结点的C++单链表实现
2023-07-13 12:05:27 深夜i     --     --
C++ 单链表 带头结点

C++单链表是一种非常常见的数据结构，它由一组节点构成，每个节点包含一个数据元素和一个指向下一个节点的指针。而带头结点的C++单链表则是在普通链表前添加了一个不存储任何元素的节点，它的作用是使得每个节点都拥有一个前驱节点，从而方便了链表的操作。本文将介绍如何使用C++实现带头结点的单链表。

一、定义节点结构体

首先，需要定义一个节点结构体，它包含两个数据成员，一个是存储数据的变量，一个是指向下一个节点的指针。

struct ListNode {

  int val;

  ListNode* next;

  ListNode(int x) : val(x), next(nullptr) {}

};

二、初始化带头结点的单链表

在创建带头结点的单链表时，需要先创建头结点。头结点的作用是指向第一个节点，并且不存储任何有意义的数据。

class MyLinkedList {

public:

  /** Initialize your data structure here. */

  MyLinkedList() {

    head = new ListNode(0);

  }

  ...

private:

  ListNode* head;

};

三、获取链表长度

链表长度是单链表中非常基本的一个操作。带头结点的单链表的长度可以理解为所有元素的数量减1。

int getLength() {

  int count = 0;

  ListNode* currentNode = head;

  while (currentNode->next) { // 遍历链表

    count++;

    currentNode = currentNode->next;

  }

  return count;

}

四、获取指定位置节点的值

在单链表中，获取指定位置节点的值需要遍历整个链表，并找到对应的位置。

int getValue(int index) {

  if (index < 0 || index >= getLength())

    return -1;

  ListNode* currentNode = head->next;

  for (int i = 0; i < index; i++)

    currentNode = currentNode->next;

  return currentNode->val;

}

五、在指定位置插入节点

在带头结点的单链表中，若要在第i个位置插入新节点，则需要遍历至第i-1个节点，修改其next指针指向新节点，并使新节点指向原第i个节点。

void addAtIndex(int index, int val) {

  if (index < 0 || index > getLength())

    return;

  ListNode* newNode = new ListNode(val);

  ListNode* currentNode = head;

  for (int i = 0; i < index; i++)

    currentNode = currentNode->next;

  newNode->next = currentNode->next;

  currentNode->next = newNode;

}

六、删除指定位置的节点

删除指定位置的节点主要需要考虑两种情况。一种是删除头结点，另一种是删除非头结点。对于非头结点的删除，需要遍历至第i-1个节点，修改其next指针指向第i+1个节点即可。

void deleteAtIndex(int index) {

  if (index < 0 || index >= getLength())

    return;

  ListNode* currentNode = head;

  for (int i = 0; i < index; i++)

    currentNode = currentNode->next;

  ListNode* temp = currentNode->next;

  currentNode->next = temp->next;

  delete temp;

}

七、完整代码

在上述操作的基础上，完整实现带头结点的C++单链表代码如下：

struct ListNode {

  int val;

  ListNode* next;

  ListNode(int x) : val(x), next(nullptr) {}

};

class MyLinkedList {

public:

  /** Initialize your data structure here. */

  MyLinkedList() {

    head = new ListNode(0);

  }

  /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */

  int get(int index) {

    if (index < 0 || index >= getLength())

      return -1;

    ListNode* currentNode = head->next;

    for (int i = 0; i < index; i++)

      currentNode = currentNode->next;

    return currentNode->val;

  }

  /** Add a node of value val before the first element of the linked list. After the insertion, the new node will

  be the first node of the linked list. */

  void addAtHead(int val) {

    ListNode* newNode = new ListNode(val);

    newNode->next = head->next;

    head->next = newNode;

  }

  /** Append a node of value val to the last element of the linked list. */

  void addAtTail(int val) {

    ListNode* newNode = new ListNode(val);

    ListNode* currentNode = head;

    while (currentNode->next)

      currentNode = currentNode->next;

    currentNode->next = newNode;

  }

  /** Add a node of value val before the index-th node in the linked list. If index equals to the length of

  linked list, the node will be appended to the end of linked list. If index is greater than the length, the

  node will not be inserted. */

  void addAtIndex(int index, int val) {

    if (index < 0 || index > getLength())

      return;

    ListNode* newNode = new ListNode(val);

    ListNode* currentNode = head;

    for (int i = 0; i < index; i++)

      currentNode = currentNode->next;

    newNode->next = currentNode->next;

    currentNode->next = newNode;

  }

  /** Delete the index-th node in the linked list, if the index is valid. */

  void deleteAtIndex(int index) {

    if (index < 0 || index >= getLength())

      return;

    ListNode* currentNode = head;

    for (int i = 0; i < index; i++)

      currentNode = currentNode->next;

    ListNode* temp = currentNode->next;

    currentNode->next = temp->next;

    delete temp;

  }

private:

  ListNode* head;

  int getLength() {

    int count = 0;

    ListNode* currentNode = head;

    while (currentNode->next) {

      count++;

      currentNode = currentNode->next;

    }

    return count;

  }

};

八、总结

带头结点的C++单链表是一种非常常见的数据结构，它的实现基于节点结构体和指针操作。本文介绍了建立头结点、获取长度、获取指定位置节点的值、在指定位置插入节点和删除指定位置的节点等5个基本操作，并给出了完整的C++实现代码。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复