C++双向链表之插入删除(两种实现)

Your task is to implement a double linked list.

Write a program which performs the following operations:

• insert x: insert an element with key x into the front of the list.
• delete x: delete the first element which has the key of x from the list. If there is not such element, you need not do anything.
• deleteFirst: delete the first element from the list.
• deleteLast: delete the last element from the list.

The input is given in the following format:

n
command1
command2
…
commandn
In the first line, the number of operations n is given. In the following n lines, the above mentioned operations are given in the following format:

insert x
delete x
deleteFirst
deleteLast

Print all the element (key) in the list after the given operations. Two consequtive keys should be separated by a single space.

7
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5

6 1 2

让你创建一个双向链表，分别进行

• i n s e r t − x : 在 链 表 头 节 点 之 后 插 入 x 值 得 结 点 insert-x:在链表头节点之后插入x值得结点 insert−x:在链表头节点之后插入x值得结点
• d e l e t e − x : 删 除 第 一 个 含 有 x 值 得 结 点 delete-x:删除第一个含有x值得结点 delete−x:删除第一个含有x值得结点
• d e l e t e L a s t : 删 除 表 尾 结 点 deleteLast:删除表尾结点 deleteLast:删除表尾结点
• d e l e t e F i r s t : 删 除 表 头 结 点 deleteFirst:删除表头结点 deleteFirst:删除表头结点

我在这里扯一点，头节点与头指针
头节点是链表的第一个物理结点，但通常为了方便程序员实现链表而设立了一个没有储存任何有效信息的节点。
头指针则是指向第一个物理结点的指针，如果链表存在头节点，那么头指针就指向头节点。
设立头结点：
①为了防止链表头为空，这样头指针就变成NULL了
②便于删除和插入，不需要特殊判断删除或者插入的位置是第一个结点还是最后一个结点，这样可以一视同仁。
③统一了对非空链表和空链表的操作。

我们首先要清楚，实现一个双向链表需要一个结点同时含有指向下个结点和上个结点的指针。

struct Node
{
    int key;
    Node *prev, *next;
};

i n i t ( ) init() init()：初始化链表，设置头节点。这里nil为头节点，是全局变量。将头节点的next和prev全部指向自身。

void init()
{
    nil = (Node *)malloc(sizeof(Node));
    nil->prev = nil;
    nil->next = nil;
}

i n s e r t ( ) insert() insert()：插入操作要注意插入语句的顺序，顺序不同可能会导致操作操作失败。

item->next = nil->next这个操作一定要在nil->next = item之前。如果先执行nil->next = item，就会改变nil->next的指向，就会导致与nil的下一个结点失去联系。

void Insert(int key)
{
    Node *item = (Node *)malloc(sizeof(Node));
    item->key = key;
    item->next = nil->next;
    nil->next->prev = item;
    nil->next = item;
    item->prev = nil;
}

d e l e t e ( N o d e ∗ t ) delete(Node *t) delete(Node∗t)：删除结点时要注意头节点不能删除，这里我选择删除的是一个指针结点，所以我们还需要一个 l i s t S e a r c h ( i n t k e y ) listSearch(int key) listSearch(intkey)来获取要删除的结点。最后删除后别忘了释放内存哟。

Node *listSearch(int key)
{
    Node *cur = nil->next;
    while (cur->key != key && cur != nil)
    {
        cur = cur->next;
    }
    return cur;
}
void Delete(Node *t)
{
    if (t == nil)
        return;
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
}
void deleteKey(int key)
{
    Delete(listSearch(key));
}

d e l e t e F i r s t ( ) 和 d e l e t e L a s t ( ) ： deleteFirst()和deleteLast()： deleteFirst()和deleteLast()：这两个无非是删除nil和下一个结点和nil的上一个结点，直接删除就好

void deleteFirst()
{
    Delete(nil->next);
}
void deleteLast()
{
    Delete(nil->prev);
}

p r i n t ( ) print() print()：最后打印输出即可，AOJ平台提交总是最后要换行，而且cin，cout经常会超时，被迫使用scanf。

void print()
{
    Node *t = nil->next;
    int i = 0;
    while (t != nil)
    {
        if (i > 0)
            printf(" ");
        printf("%d", t->key);
        i++;
        t = t->next;
    }
    printf("n");
}

最后附上完整代码

#include 
using namespace std;
struct Node
{
    int key;
    Node *prev, *next;
};
Node *nil;
void init()
{
    nil = (Node *)malloc(sizeof(Node));
    nil->prev = nil;
    nil->next = nil;
}
void Insert(int key)
{
    Node *item = (Node *)malloc(sizeof(Node));
    item->key = key;
    item->next = nil->next;
    nil->next->prev = item;
    nil->next = item;
    item->prev = nil;
}
Node *listSearch(int key)
{
    Node *cur = nil->next;
    while (cur->key != key && cur != nil)
    {
        cur = cur->next;
    }
    return cur;
}
void Delete(Node *t)
{
    if (t == nil)
        return;
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
}
void deleteFirst()
{
    Delete(nil->next);
}
void deleteLast()
{
    Delete(nil->prev);
}
void deleteKey(int key)
{
    Delete(listSearch(key));
}
void print()
{
    Node *t = nil->next;
    int i = 0;
    while (t != nil)
    {
        if (i > 0)
            printf(" ");
        printf("%d", t->key);
        i++;
        t = t->next;
    }
    printf("n");
}
int main()
{
    int n;
    char com[20];
    int key;
    scanf("%d", &n);
    init();
    for (int i = 0; i < n; i++)
    {
        scanf("%s%d", com, &key);
        if (com[0] == 'i')
            Insert(key);
        else if (com[0] == 'd')
        {
            if (strlen(com) > 7)
            {
                if (com[6] == 'F')
                    deleteFirst();
                else
                    deleteLast();
            }
            else
                deleteKey(key);
        }
    }
    print();
    return 0;
}

这是使用了C++模板库List

#include 
using namespace std;
int main()
{
    int n, x;
    char com[20];
    list lt;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", com);
        scanf("%d", &x);
        if (com[0] == 'i')
        {
            lt.push_front(x);
        }
        else
        {
            if (strlen(com) > 6)
            {
                if (com[6] == 'F')
                    lt.pop_front();
                else
                    lt.pop_back();
            }
            else
            {
                for (list::iterator it = lt.begin(); it != lt.end(); it++)
                {
                    if (*it == x)
                    {
                        lt.erase(it);
                        break;
                    }
                }
            }
        }
    }
    int i = 0;
    for (list::iterator it = lt.begin(); it != lt.end(); it++)
    {
        if (i > 0)
            printf(" ");
        printf("%d", *it);
    }
    printf("n");
}

这里题目网址