資料結構/連結串列

連結串列是一種簡單的方式來儲存未知數量的元素。記憶體分配有兩個主要函式 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);
}

備註

如您所見，兩種操作的雙鏈表版本都更優雅。