鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲下一個(gè)結(jié)點(diǎn)地址的指針域。相比于線性表順序結(jié)構(gòu)，操作復(fù)雜。由于不必須按順序存儲，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問特定編號的節(jié)點(diǎn)則需要O(n)的時(shí)間，而線性表和順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。
使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開銷比較大。鏈表明顯的好處就是，常規(guī)數(shù)組排列關(guān)聯(lián)項(xiàng)目的方式可能不同于這些數(shù)據(jù)項(xiàng)目在記憶體或磁盤上順序，數(shù)據(jù)的存取往往要在不同的排列順序中轉(zhuǎn)換。鏈表允許插入和移除表上任意位置上的節(jié)點(diǎn)，但是不允許隨機(jī)存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環(huán)鏈表。鏈表可以在多種編程語言中實(shí)現(xiàn)。像Lisp和Scheme這樣的語言的內(nèi)建數(shù)據(jù)類型中就包含了鏈表的存取和操作。程序語言或面向?qū)ο笳Z言，如C,C++和Java依靠易變工具來生成鏈表。
其中存儲數(shù)據(jù)元素信息的域稱作數(shù)據(jù)域（設(shè)域名為data），存儲直接后繼存儲位置的域稱為指針域（設(shè)域名為next）。指針域中存儲的信息又稱做指針或鏈。
由分別表示,，…，的N 個(gè)結(jié)點(diǎn)依次相鏈構(gòu)成的鏈表，稱為線性表的鏈?zhǔn)酱鎯Ρ硎荆捎诖祟愭湵淼拿總€(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，故又稱單鏈表或線性鏈表。
linkedlist.h ?//頭文件，定義節(jié)點(diǎn)和鏈表信息及聲明創(chuàng)建、插入、刪除等基本函數(shù)
/*鏈表的實(shí)現(xiàn)，實(shí)現(xiàn)創(chuàng)建、插入、刪除等操作*/
#include <string>
using namespace std;
struct StuInfo
{
int id; //學(xué)號
string name; //姓名
};
struct Node
{
StuInfo info;
Node *next;
Node(){}
Node(StuInfo x){ info = x; next = NULL; }
};
class LinkedList
{
public:
LinkedList(); //構(gòu)造函數(shù)
~LinkedList(); //析構(gòu)函數(shù)
void insert(StuInfo info, int pos);
void remove(int id); //根據(jù)學(xué)生學(xué)號進(jìn)行刪除
int find(int id); //根據(jù)學(xué)號進(jìn)行查找，返回節(jié)點(diǎn)位置
int getLength(); //獲得鏈表長度
void print(); //打印鏈表信息
private:
Node *head;
int length;
};
下面繼續(xù)編寫對應(yīng)的源文件，linkedlist.cpp ?//實(shí)現(xiàn)具體函數(shù)內(nèi)容
#include <iostream>
#include "linkedlist.h"
using namespace std;
//構(gòu)造函數(shù)
LinkedList::LinkedList()
{
head = NULL;
length = 0;
}
//析構(gòu)函數(shù)
LinkedList::~LinkedList()
{
Node* temp;
for (int i = 0; i < length; i++)
{
temp = head;
head = head->next;
delete temp;
}
}
void LinkedList::insert(StuInfo info, int pos)
{
if (pos < 0)
{
cout << "節(jié)點(diǎn)位置必須是正整數(shù)" << endl;
}
int index = 1;
Node *temp = head;
Node *node = new Node(info);
if (pos == 0)
{
node->next = temp;
head = node;
length++;
return;
}
while (index < pos && temp != NULL)
{
temp = temp->next;
index++;
}
if (temp == NULL)
{
cout << "插入失敗，位置序號超過鏈表長度" << endl;
return;
}
node->next = temp->next;
temp->next = node;
length++;
return;
}
void LinkedList::remove(int id)
{
int pos = find(id);
if (pos == -1)
{
cout << "鏈表中沒有該學(xué)號，無法刪除對應(yīng)信息" << endl;
return;
}
if (pos == 0)
{
head = head->next;
length--;
return;
}
int index = 1;
Node *temp = head;
while (index < pos)
{
temp = temp->next;
}
temp->next = temp->next->next;
length--;
return;
}
int LinkedList::find(int id)
{
Node *temp = head;
int index = 0;
while (temp != NULL)
{
if (temp->info.id == id)
{
return index;
}
temp = temp->next;
index++;
}
return -1;
}
int LinkedList::getLength()
{
return length;
}
void LinkedList::print()
{
if (head == NULL)
{
cout << "鏈表為空，沒有信息" << endl;
return;
}
Node *temp = head;
while (temp != NULL)
{
cout << temp->info.id << "," << temp->info.name << endl;
temp = temp->next;
}
cout << endl;
return;
}
，編寫測試用的main函數(shù)
#include <iostream>
#include <string>
#include "linkedlist.h"
using namespace std;
int main()
{
LinkedList head;
StuInfo info1, info2, info3, info4, info5;
info1.id = 1001, info1.name = "張三", info2.id = 1002, info2.name = "莉絲", info3.id = 1003, info3.name = "李武", info4.id = 1004, info4.name = "六南", info5.id = 1005, info5.name = "琪琪";
//測試插入數(shù)據(jù)
cout << "測試插入：" << endl;
head.insert(info1, 0);
head.print();
head.insert(info2, 1);
head.print();
head.insert(info3, 4);
head.print();
head.insert(info4, 0);
head.print();
head.insert(info5, 2);
head.print();
//測試刪除數(shù)據(jù)
cout << "測試刪除：" << endl;
cout << "鏈表長度為：" << head.getLength() << endl;
head.remove(1004);
head.print();
cout << "鏈表長度為：" << head.getLength() << endl;
head.remove(1004);
head.print();
return 0;
}