以排序方式将节点插入双向链表？

Question

我正在解决一个问题，我有一个方法应该以排序的方式将节点插入到双向链表中。这是我的节点和列表结构：

typedef struct NodeStruct Node;

//struct for each office item
struct NodeStruct {
    int id;
    struct NodeStruct *next;
    struct NodeStruct *prev; //Create doubly linked list node
};


/** Structure for the whole list, including head and tail pointers. */
typedef struct {
  /** Pointer to the first node on the list (or NULL ). */
  Node *head;
  Node *last;
} List;

当我尝试打印项目列表时，我尝试插入的项目没有出现。例如，如果我尝试将 15 插入此列表

1 -> 2 -> 3 -> 5 -> 7，

15没有出现在最后。这是我的插入方法：

void insert(int idInsert, List *list)
{
  //Initialize data for node
  int idInsert;

  //Insert the record based on the ID if no duplicates exist
  //Special case: insert at front if idInsert is less than the ID of the current head
  if (idInsert < list->head->id) {
    //Make the node with idInsert the first node
    Node *new = (Node *)malloc(sizeof(Node)); //Allocate memory for the new node

    //Add in data
    new->id = idInsert;

    new->next = list->head;

    list->head = new;
  } else { //Locate the node before the point of insertion
    //Allocate memory for the node
    Node *new = (Node *)malloc(sizeof(Node));

    //Add in data
    new->id = idInsert;

    Node *current = list->head;
    while (current->next != NULL && current->next->id < new->id) {
      current = current->next;
    }
    new->next = current->next;
    if (current->next != NULL) {
      new->next->prev = new;
    }
    current->prev->next = new;
    new->prev = current;
  }

  //Print this message if successful
  printf("RECORD INSERTED: %d\n", idInsert);
  }

我还将在下面包含一些最小的可重现代码：

#include <stdlib.h>
#include <stdio.h>


typedef struct NodeStruct Node;

//struct for each office item
struct NodeStruct {
    int id;
    struct NodeStruct *next;
    struct NodeStruct *prev; //Create doubly linked list node
};


/** Structure for the whole list, including head and tail pointers. */
typedef struct {
  /** Pointer to the first node on the list (or NULL ). */
  Node *head;
  Node *last;
} List;

List *list;

List *makeList();
void insert(int idInsert, List *list);
static void *addRecord(List *list, int newID);
static void printReverse(List *list);

int main(int argc, char **argv) {

  //Create an empty list for you to start.
  list = (List *)makeList();

  addRecord(list, 1);
  addRecord(list, 2);
  addRecord(list, 3);
  addRecord(list, 4);
  addRecord(list, 7);
  insert(15, list);
  printReverse(list);

}

List *makeList()
{
  List *list = (List *) malloc( sizeof( List ) );
  list->head = NULL;
  list->last = NULL;
  return list;
}

void insert(int idInsert, List *list)
{
  //Insert the record based on the ID if no duplicates exist
  //Special case: insert at front if idInsert is less than the ID of the current head
  if (idInsert < list->head->id) {
    //Make the node with idInsert the first node
    Node *new = (Node *)malloc(sizeof(Node)); //Allocate memory for the new node

    //Add in data
    new->id = idInsert;

    new->next = list->head;

    list->head = new;
  } else { //Locate the node before the point of insertion
    //Allocate memory for the node
    Node *new = (Node *)malloc(sizeof(Node));

    //Add in data
    new->id = idInsert;

    Node *current = list->head;
    while (current->next != NULL && current->next->id < new->id) {
      current = current->next;
    }
    new->next = current->next;
    if (current->next != NULL) {
      new->next->prev = new;
    }
    current->prev->next = new;
    new->prev = current;
  }

  //Print this message if successful
  printf("RECORD INSERTED: %d\n", idInsert);
}

static void *addRecord(List *list, int newID) {
    //Allocate memory for the node
    Node *new = (Node *)malloc(sizeof(Node)); 

    //Add in data
    new->id = newID; 
    new->prev = NULL;

    //New node has no next, yet
    new->next = NULL;

    Node **next_p = &list->head;
    while (*next_p) {
        next_p = &(*next_p)->next;
    }
    *next_p = new;
    list->last = new;
    new->prev = *next_p;

    return EXIT_SUCCESS;
}

static void printReverse(List *list) {
    Node **tail = &list->last;
    printf("LIST IN REVERSE ORDER:\n");

    //Traversing until tail end of linked list
    while (*tail) {
        printf("Item ID: %d\n", (*tail)->id);
        tail = &(*tail)->prev;
    }
}

我的 addRecord 方法似乎工作正常（此功能用于将值添加到链表的末尾），但我的 insert 方法工作不正常。当我执行上面的最小可重现代码时，我陷入了无限循环。调用 printReverse 后我想要的结果是：

Item ID: 15
Item ID: 7
Item ID: 4
Item ID: 3
Item ID: 2
Item ID: 1

有人可以指出我的插入方法出了什么问题吗？

Answer 1

插入有三种情况：

在开头插入。
在中间插入。
在最后插入。

您绘制算法草图的武器是一张纸和一支铅笔，您可以在上面画出您的代码正在做什么。

在开头插入

你的开头插入的情况不完整，因为你需要将新节点的前一个指针设置为NULL，而旧节点的前一个指针现在应该指向新创建的节点.

可以这样做：

Node *new = malloc(sizeof(Node)); //Allocate memory for the new node

list->head->prev = new;
new->prev = NULL;
// rest of your code

最后插入

无论如何，要回答您的问题，在您的示例中，您可以简单地使用 addRecord() 方法在列表中追加一个节点，当要插入的节点结束时，就像在您的示例中一样，id 为 15 的节点。

你可以这样做：

Node *current = list->head;
while (current->next != NULL && current->next->id < new->id) {
  current = current->next;
}
// if the new node is the last one
if(current->next == NULL)
{
  // append it to the list
  addRecord(list, idInsert);
  printf("RECORD INSERTED: %d\n", idInsert);
  return;
}

假设您使用的是您之前中讨论的方法 addRecord()，而不是您在此处提供的方法。

但是正如@SomeProgrammerDude 评论的那样，您可以通过检查新节点是否大于最后一个节点来简化它，如果是，则调用 addRecord().

中间插入

如果列表中只有 ID 为 1 的节点，而您在末尾插入 ID 为 15 的节点，这将调用 未定义行为:

current->prev->next = new;

由于当前节点（id 1）没有上一个节点，因此设置为NULL。因此，您请求的 next 字段不是结构或联合。与列表中已有 1 和 15 并尝试插入 5 相同。

尝试将其更改为：

current->next = new;

但是，使用您的代码，您将请求 list->head 的 id，即使列表为空，这意味着 head（和 last）指针一片空白。这将调用 Undefined Behavior (UB)，这可能会导致分段错误。

因此，在下面的代码中，我将首先检查列表是否为空，或者是否应在末尾插入新节点，因为在这两种情况下，只需调用 addRecord()方法（将节点附加到列表）。

if 语句的条件将是这样的：

if (list->last == NULL || idInsert > list->last->id)

由于短路，将按以下顺序进行评估：

如果最后一个指针为 NULL，则条件肯定会被评估为真，因为运算符是逻辑或，因此单个真操作数就足以确定条件的总体结果是什么.这意味着，它不会评估第二个操作数，因此不会取消引用最后一个指针（这将调用 UB，因为我们将请求 NULL 的 id）。

把所有东西放在一起：

#include <stdlib.h>
#include <stdio.h> 

typedef struct NodeStruct Node;

//struct for each office item
struct NodeStruct {
    int id;
    struct NodeStruct *next;
    struct NodeStruct *prev; //Create doubly linked list node
};

/** Structure for the whole list, including head and tail pointers. */
typedef struct {
  /** Pointer to the first node on the list (or NULL ). */
  Node *head;
  Node *last;
} List;

List *list;

List *makeList();
void insert(int idInsert, List *list);
static void *addRecord(List *list, int newID);
static void printReverse(List *list);

int main(void) {

  //Create an empty list for you to start.
  list = (List *)makeList();

  addRecord(list, 1);
  addRecord(list, 2);
  addRecord(list, 3);
  addRecord(list, 4);
  addRecord(list, 7);
  insert(6, list);
  insert(0, list);
  insert(15, list);
  printReverse(list);

}

List *makeList()
{
  List *list = (List *) malloc( sizeof( List ) );
  list->head = NULL;
  list->last = NULL;
  return list;
}

//Insert the record based on the ID if no duplicates exist
void insert(int idInsert, List *list)
{
  // Insert at end, if list is empty or if id is greater than all existing ids
  // Short circuting protects from derefercing a NULL pointer
  if (list->last == NULL || idInsert > list->last->id) {
    addRecord(list, idInsert);
  } else if (idInsert < list->head->id) {  // Insert at start
    //Make the node with idInsert the first node
    Node *new = malloc(sizeof(Node)); //Allocate memory for the new node

    list->head->prev = new;
    new->prev = NULL;
    //Add in data
    new->id = idInsert;

    new->next = list->head;

    list->head = new;
  } else { // Insert in the middle
    //Locate the node before the point of insertion
    //Allocate memory for the node
    Node *new = malloc(sizeof(Node));

    //Add in data
    new->id = idInsert;

    Node *current = list->head;
    while (current->next != NULL && current->next->id < new->id) {
      current = current->next;
    }
    new->next = current->next;
    if (current->next != NULL) {
      new->next->prev = new;
    }
    current->next = new;
    new->prev = current;
  }

  //Print this message if successful
  printf("RECORD INSERTED: %d\n", idInsert);
}

static void *addRecord(List *list, int newID) 
{
  //Allocate memory for the node
  Node *new = malloc(sizeof(Node)); 

  //Add in data
  new->id = newID; 

  new->prev = list->last;
  new->next = NULL;

  list->last = new;

  // if list is empty
  if(!list->head)
  {
    list->head = new;
    return EXIT_SUCCESS;
  }

  Node **next_p = &list->head;
  while (*next_p) {
    next_p = &(*next_p)->next;
  }
  *next_p = new;

  return EXIT_SUCCESS;
}

static void printReverse(List *list) {
    Node **tail = &list->last;
    printf("LIST IN REVERSE ORDER:\n");

    //Traversing until tail end of linked list
    while (*tail) {
        printf("Item ID: %d\n", (*tail)->id);
        tail = &(*tail)->prev;
    }
}

输出：

RECORD INSERTED: 6
RECORD INSERTED: 0
RECORD INSERTED: 15
LIST IN REVERSE ORDER:
Item ID: 15
Item ID: 7
Item ID: 6
Item ID: 4
Item ID: 3
Item ID: 2
Item ID: 1
Item ID: 0

附录

请注意在处理中间情况之前，我是如何处理在开始和结束处插入的特殊情况的。那是因为你的列表有 head 和 last 指针，这些特殊的插入可以在恒定时间内完成，O(1)，因为你不必扫描（迭代）列表。

但是在中间插入的时候，需要扫描链表，找到合适的索引，然后在那个索引处插入节点。

记住：遍历列表的操作可能需要线性时间（遍历整个列表），用渐近表示法是 O(n)，其中 n 是列表的大小。

PS：我还使用链接问题中讨论的打印（按正常顺序）方法检查了 next 指针。

PPS: 完成后，不要忘记释放列表。我在 List (C) 中有一个方法，这与双链表相同，除了你还必须将头指针和最后指针也设置为 NULL。

以排序方式将节点插入双向链表？

Insert a node into a doubly linked list in a sorted manner?

c

sorting

data-structures

doubly-linked-list

insertion

在开头插入

最后插入

中间插入

附录