单链表尾巴

Question

如果你想创建一个像这样的单链表：

struct Node { 
    int data;
    Node *next;
};

struct List{ 
    Node *head;
    // Node *tail; --> necessary?
    Node *last;
};

这个列表有方法“追加”、“删除”、“printList”和“findElement”。有必要有尾巴吗？因为使用“最后”你可以地址最后一个节点。

那么，什么时候有必要拥有所有三个节点“头”、“尾”和“最后”？例如，当您想将排序的节点插入列表时？

Answer 1

我认为这取决于你想使用什么操作。

>

假设您希望插入和删除列表末尾的节点，那么在列表中保留最后一个节点肯定是明智的选择。

否则，如果要在列表开头执行操作，则不需要最后一个节点。

Answer 2

实际上，您可以实现排队（在尾部追加）、推（在头部前置）、出列（从头部移除），当然还可以使用一个指针头查找和打印。诀窍是使列表循环并使标题指向尾部。然后tail-

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

typedef struct node_s {
  struct node_s *next;
  int data;
} Node;

typedef struct list_s {
  Node *tail;
} List;

Node *new_node(int data) {
  Node *node = malloc(sizeof *node);
  node->data = data;
  node->next = node;
  return node;
}

void init_list(List *list) {
  list->tail = NULL;
}

int is_empty(List *list) {
  return list->tail == NULL;
}

void enqueue(List *list, Node *node) {
  if (list->tail) {
    Node *head = list->tail->next;
    node->next = head;
    list->tail->next = node;
    list->tail = node;
  } else list->tail = node->next = node;
}

void push(List *list, Node *node) {
  if (list->tail) {
    Node *head = list->tail->next;
    node->next = head;
    list->tail->next = node;
  } else list->tail = node->next = node;
}

Node *dequeue(List *list) {
  Node *head = list->tail->next;
  if (head == list->tail)
    list->tail = NULL;
  else
    list->tail->next = head->next;
  return head;
}

void print_list(List *list) {
  printf("The list:\n");
  if (list->tail) {
    Node *head = list->tail->next;
    Node *p = head;
    do {
      printf("%d\n", p->data);
      p = p->next;
    } while (p != head);
  }
}

int main(int argc, char *argv[]) {
  List list[1];
  init_list(list);

  // Build the list in order and print it.
  for (int i = 0; i < 4; i++) enqueue(list, new_node(i));
  print_list(list);

  // Remove elements from head until empty.
  printf("Dequeueing:\n");
  while (!is_empty(list)) {
    Node *node = dequeue(list);
    printf("%d\n", node->data);
    free(node);
  }

  // Build the list in reverse order and print it.
  for (int i = 0; i < 4; i++) push(list, new_node(i));
  print_list(list);

  return 0;
}

Answer 3

不，没有必要。尾部等于头部-

还要注意，字段last有点不寻常。在大多数用例中，您将元素添加到单链表的头部，并在真正需要添加到末尾时使用不同的数据结构。