APS105预习 - 12

Chapter 13 Linked List 链表

继续写链表的封装

链表的封装

将节点插入有序链表中

bool insertIntoOrderedList(LinkedList *orderedList, int value) {
  // orderedList is in an ascending order
  Node *current = orderedList->head;

  if (current->data > value) {
    return insertAtFront(orderedList, value);
  }

  while (current->next != NULL && current->next->data < value) {
    current = current->next;
  }

  Node *tmp = createNode(value);
  if (tmp == NULL) {
    return false;
  }

  tmp->next = current->next;
  current->next = tmp;

  return true;
}

该代码有三个需要注意的点：

• 判断新节点内存分配是否成功
• 处理插入值位于链表末尾的情况
• 处理插入值位于链表开头的情况

删除链表开头的节点

void deleteFront(LinkedList *list) {
  if (list->head == NULL) {
    return;  // if the linked list is empty, do nothing
  }
  Node *tmp = list->head->next;  // save the new head node
  free(list->head);
  list->head = tmp;
}

注意检查列表是否为空！

删除链表末尾的节点

void deleteBack(LinkedList *list) {
  if (list->head == NULL) {  // there is no node in linked list
    return;
  }
  if (list->head->next == NULL) {  // there is only one node in linked list
    deleteFront(list);
  }

  // find the second last node
  Node *current = list->head;
  while (current->next->next != NULL) {
    current = current->next;
  }

  free(current->next);
  current->next = NULL;
}

注意特殊判断链表为空和链表仅有一个元素的情况

删除链表所有的节点 (释放内存)

int deleteAllNodes(LinkedList *list) {
  int numDeletedNodes = 0;

  while (list->head != NULL) {
    deleteFront(list);
    numDeletedNodes++;
  }

  return numDeletedNodes;
}

删除第一个匹配的节点

在遍历链表的过程中，是没有办法找到上一个遍历的节点的，所以我们需要让遍历指针停在目标节点的前一个节点。但是这样又回导致第一个节点无法被遍历，所以，要特殊判断第一个节点是否是我们要删除的节点。

bool deleteFirstMatch(LinkedList *list, int searchVal) {
  Node *current = list->head;
  if (current->data == searchVal) {
    deleteFront(list);
    return true;
  }

  while (current->next != NULL && current->next->data != searchVal) {
    current = current->next;
  }

  // current now points to a node just before the node that matched,
  // OR current points to the last node.
  if (current->next != NULL) {
    Node *tmp = current->next;
    current->next = tmp->next;
    free(tmp);
    return true;
  }

  return false;
}

删除所有匹配的节点

int deleteAllMatch(LinkedList *list, int searchVal) {
  int numDeleted = 0;
  while (deleteFirstMatch(list, searchVal)) {
    numDeleted++;
  }

  return numDeleted;
}

利用删除第一个匹配节点的函数，可以很轻松的实现删除所有匹配节点。这个函数的性能依然存在优化空间。