鏈表是指由一系列儲(chǔ)存在非連續(xù)儲(chǔ)存空間結(jié)點(diǎn)組成的儲(chǔ)存結(jié)構(gòu)。每個(gè)結(jié)點(diǎn)由兩部分組成：一是儲(chǔ)存元素的數(shù)據(jù)域，一是儲(chǔ)存下一個(gè)節(jié)點(diǎn)地址的指針域。用數(shù)組模擬鏈表可以十分清晰明了地理解這一定義。

在這里，我們簡(jiǎn)單地介紹一下單鏈表和雙鏈表兩種鏈表以及用數(shù)組模擬實(shí)現(xiàn)它們的方式。

1.單鏈表

單鏈表是指針?lè)较騿蜗虻逆湵恚碼結(jié)點(diǎn)的指針域儲(chǔ)存著b結(jié)點(diǎn)的地址，而b結(jié)點(diǎn)的指針域內(nèi)沒(méi)有儲(chǔ)存a結(jié)點(diǎn)的地址。在訪問(wèn)時(shí)，可以由a到b訪問(wèn)，而不能由b到a訪問(wèn)。

單鏈表

如圖可以清晰地看到，各個(gè)結(jié)點(diǎn)的指向都是單向的。

Q: 那么，如何用數(shù)組來(lái)實(shí)現(xiàn)它呢？

A: 方法如下

在k結(jié)點(diǎn)右側(cè)插入元素x。先將x賦值給該節(jié)點(diǎn)的數(shù)據(jù)域（e[idx]），然后將k結(jié)點(diǎn)的指針域賦值給該結(jié)點(diǎn)的指針域，最后將k結(jié)點(diǎn)的指針域儲(chǔ)存的地址改為該節(jié)點(diǎn)的地址。

void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

刪除k結(jié)點(diǎn)指向的結(jié)點(diǎn)。這里所指的刪除，是將k的指向改為該結(jié)點(diǎn)的指向。原本為a -> b -> c，改為a -> c，b結(jié)點(diǎn)依然存在，只是沒(méi)有其他結(jié)點(diǎn)指向它，也就無(wú)法通過(guò)鏈表訪問(wèn)它，我們認(rèn)為它就再鏈表上被刪除了。

void remove(int k)
{
    ne[k] = ne[ne[k]];
}

讀取鏈表。讀取鏈表只用注意一點(diǎn)，在用單指針掃描時(shí)不是將指針位置右移，而是將指針移動(dòng)到該結(jié)點(diǎn)指向的位置。

for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
cout << endl;

主要的操作就是如此，下邊看看完整代碼：

這是較為經(jīng)典的寫(xiě)法，我個(gè)人認(rèn)為有些麻煩，head不必單獨(dú)拿出來(lái)寫(xiě)一個(gè)函數(shù)。但是有助于理解。

#include<iostream>
using namespace std;

const int M = 1e5 + 10;

int m, k, x, idx, head;
int e[M], ne[M];

void init()
{
    head = -1, idx = 0;
}

void add_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

void remove(int k)
{
    ne[k] = ne[ne[k]];
}

void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

int main()
{
    init();

    cin >> m;
    while (m--)
    {
        char op;
        cin >> op;

        if (op == 'H')
        {
            cin >> x;
            add_head(x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (!k) head = ne[head];
            remove(k - 1);
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}

這種寫(xiě)法稍微簡(jiǎn)便一些，用a[0]替代head。

#include<iostream>
using namespace std;

const int M = 1e5 + 10;

int m, k, x, idx, head;
int e[M], ne[M];

void init()
{
    ne[0] = -1, idx = 1;
}

void remove(int k)
{
    ne[k] = ne[ne[k]];
}

void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

int main()
{
    init();

    cin >> m;
    while (m--)
    {
        char op;
        cin >> op;

        if (op == 'H')
        {
            cin >> x;
            add(0, x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (!k) head = ne[head];
            remove(k);
        }
        else
        {
            cin >> k >> x;
            add(k, x);
        }
    }

    for (int i = ne[0]; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}

2.雙鏈表

雙鏈表顧名思義就是指針?lè)较螂p向的鏈表。

雙鏈表

可以看到除了頭尾他們的指針都是雙向的。

它的實(shí)現(xiàn)方法如下：

創(chuàng)建開(kāi)始和結(jié)束結(jié)點(diǎn)。0表示開(kāi)始，1表示結(jié)束，互相指向，在插入時(shí)直接往中間插入即可。

void init()
{
	r[0] = 1, l[1] = 0;
	idx = 2;
}

插入結(jié)點(diǎn)。雙鏈表插入結(jié)點(diǎn)的方法與單鏈表相同，但是操作要稍微復(fù)雜一些，這是在k結(jié)點(diǎn)右邊插入一結(jié)點(diǎn)的代碼。它要顧及結(jié)點(diǎn)左右的結(jié)點(diǎn)指向，對(duì)于兩邊都要操作。面臨在k結(jié)點(diǎn)左邊插入一結(jié)點(diǎn)時(shí)，不必單獨(dú)在寫(xiě)一個(gè)函數(shù)，而改成在l[k]結(jié)點(diǎn)的右邊插入一個(gè)結(jié)點(diǎn)。

void add(int k, int x)
{
	a[idx] = x;
	r[idx] = r[k], l[idx] = l[r[k]];
	l[r[k]] = idx, r[k] = idx;
	idx++;
}

刪除節(jié)點(diǎn)。刪除結(jié)點(diǎn)與插入結(jié)點(diǎn)同理，我就不多贅述了。

void remove(int k)
{
	r[l[k]] = r[k];
	l[r[k]] = l[k];
}

輸出鏈表?？梢赃x擇輸出方向，這里是從左往右輸出。

for (int i = r[0]; i != 1; i = r[i])cout << a[i] << ' ';
	cout << endl;

以下是完整代碼：

#include<iostream>
using namespace std;

const int N = 1e5 + 10;

int a[N], l[N], r[N];
int idx;
int m;

void init()
{
	r[0] = 1, l[1] = 0;
	idx = 2;
}

void add(int k, int x)
{
	a[idx] = x;
	r[idx] = r[k], l[idx] = l[r[k]];
	l[r[k]] = idx, r[k] = idx;
	idx++;
}

void remove(int k)
{
	r[l[k]] = r[k];
	l[r[k]] = l[k];
}

int main()
{
	init();
	cin >> m;
	while (m--)
	{
		int k, x;
		string op;
		cin >> op;
		if (op == "L")
		{
			cin >> x;
			add(0, x);
		}
		else if (op == "R")
		{
			cin >> x;
			add(l[1], x);
		}
		else if (op == "D")
		{
			cin >> k;
			remove(k + 1);
		}
		else if (op == "IL")
		{
			cin >> k >> x;
			add(l[k + 1], x);
		}
		else if (op == "IR")
		{
			cin >> k >> x;
			add(k + 1, x);
		}
	}

	for (int i = r[0]; i != 1; i = r[i])cout << a[i] << ' ';
	cout << endl;
	return 0;
}