数据结构/链表

链表是一种简单的方式来存储未知数量的元素。内存分配有两个主要函数 malloc() 和 calloc()。例如，您可能需要一个程序来接受一堆数字，然后计算平均值。

您可以像这样动态分配数组

int i;
scanf("enter size of array to create: %d.\n", &i);
int *array = (int*)malloc(sizeof(int) * i);

或者在 C++ 中使用这种方式

int i;
cout << "Enter the size of the array to create:";
cin >> i;
int *array = new int[i];

但是，事先知道数组需要多大往往是不可能的。每次调整数组大小都需要进行内存分配和所有元素的复制，这效率低下（尽管可以通过按当前大小比例调整数组大小来抵消，这是标准模板库矢量模板中使用的技术）。

您可以像这样创建一个足够大的数组来覆盖所有预期情况

int array[10000]; /* oughtta cover all situations. */

这效率低下，因为它始终会消耗 10,000 个 int 的大小，这可能是 19Kb 到 39Kb 之间的任何值。

引入链表。链表是一个可增长的容器，允许快速插入和删除操作。这允许在不重新分配整个结构的情况下将项目追加到列表的末尾。

链表的结构可能类似于以下内容

typedef struct _ListItem {
  int data; //data to store here it is a integer
  struct _ListItem *next; //pointer to the next item's address in the list
} ListItem;

由于数据类型可能是其他类型，因此每次需要不同类型时都重写它会很麻烦，因此通常在 C++、C# 或其他支持泛型的语言中实现为模板类。将链表封装在类中作为抽象数据类型允许将头和尾的概念抽象出来，远离程序员。这也允许基本操作根据需要修改头或尾。

双向链表

这是链表的专用版本，它允许双向遍历。普通链表只能从头到尾遍历。双链表允许以从尾到头的顺序遍历列表，代价是需要更多的内存和一些稍微更昂贵的操作。对于双链表，您需要跟踪尾部，除了跟踪头部之外。

操作

链表中使用了几种基本操作。许多这些操作使用位置作为参数。此参数是指向 ListItem 的指针，因为 ListItem 代表链中的一个项目（包括指向下一个项目的链接）。单链表操作将要突变的元素（插入或删除）之前的直接位置作为参数。使用前一个位置的原因是因为对于单链表，没有办法找到前一个位置以更新链接。如果需要通用函数，这意味着为了突变第一个项目，必须使用虚拟头项目。这是双链表的优势之一的示例，因为我们可以使用指向我们要突变的实际项目的指针，因为存在指向前一个项目的指针，因此我们可以更新链接。

插入

插入操作以位置和要插入的新项目作为参数。

单链表版本

void insert(unsigned int position, ListItem *item, ListItem **head){
  ListItem *current = *head;
  unsigned int cntr=0;
  while (current->next != NULL) {
    current = current->next;
    cntr++;
  }
  if(position==0){
    item->next = *head;
    *head = item;
  }
  else if(position>=cntr){
    current->next=item;
    current->next->next = NULL;
  }
  else{
    current = *head;
    for(int i=0;i<position-1;i++){
      current=current->next;
    }
    item->next=current->next;
    current->next=item;
  }
}

双链表版本

void insert(ListItem *position, ListItem *item)
{
   item->next = position->next;
   position->next = item;
   item->prev=position;
 }

删除

删除操作以位置作为参数并将其删除。

单链表版本

// position is immediately before the item we want to delete
void delete(ListItem *position)
{
   if(0 == position->next) return;
   ListItem* temp = position->next->next;
   free(position->next);
   position->next = temp;
}

双链表版本

// position is the actual item we want to delete
void delete(DL_ListItem *position)
{
   if(position->next)
      position->next->prev = position->prev;
   if(position->prev)
      position->prev->next = position->next;
   free(position);
}

备注

如您所见，两种操作的双链表版本都更优雅。