Link_List

#include <iostream>
using namespace std;
#define LISTSIZE 1000
//LinkedList API
typedef struct ListNode {
int key;
struct ListNode * next;
struct ListNode * prev;
}ListNode;
ListNode ListNodePool[LISTSIZE];
int NodeNum = 0;
ListNode *NIL;

ListNode * getNewNode(){
return & ListNodePool[NodeNum++];
}

void listInit(){
NIL->next = NIL;//.用于实例化的对象操作，->用于指针对象的操作
NIL->prev = NIL;
NIL->key = 0;
}

void listInsertAtFront(ListNode * node){//先连后断，把节点插入到NIL的后面
node->next = NIL->next;
node->prev = NIL;
NIL->next->prev = node;
NIL->next = node;
}

void listInsertAfter(ListNode * dstNode, ListNode * NewNode){//先连后断，插入到dstNode后面
NewNode->next = dstNode->next;//右左左右 先把New的连上然后再处理NewNode后面节点的prev，最后连接dstNode的next
NewNode->prev = dstNode;//或者理解为先两个向外指出的，然后两个向内指入的。
dstNode->next->prev = NewNode;
dstNode->next = NewNode;
}

void listDelete(ListNode * node){//先处理node前一个节点的next,然后处理node后一个节点的prev。
node->prev->next = node->next;
node->next->prev = node->prev;
}

ListNode * listSearch(int k){
ListNode * x = NIL->next;
while(x != NIL && x->key != k){
x = x->next;
}
return x;
}

//end of LinkedList API

int data[LISTSIZE];

void insertSort(int data[], int N){//data[]代表要插入的数据，N代表个数
for(int i = 1; i < N; i++){
int key = data[i];
int j;
for(j = i - 1; j >= 0; j--){
if(data[j] > key){
data[j + 1] = data[j];
}else{
break;
}
}
data[j + 1] = key;
}
}

void showData(int N){
for(int i = 0; i < N; i++){
cout << data[i] << " ";
}
cout << endl;
}

void showList(){
ListNode * curNode = NIL->next;
while(curNode != NIL){
cout << curNode->key << " ";
curNode = curNode->next;
}
cout << endl;
}

void listInsertSort(){

ListNode * curNode = NIL->next->next;
ListNode * tmpNode;
while(curNode != NIL){
//cout << curNode->key << " " << endl;
ListNode * dstNode = NIL->next;
while(dstNode != curNode && dstNode->key < curNode->key){
dstNode = dstNode->next;//相当于数组里面的j--且j>=0
}

dstNode = dstNode->prev;
tmpNode = curNode->next;//进行下一次循环的准备，因为delete了curnode，所以需要提前保存。
listDelete(curNode);
listInsertAfter(dstNode, curNode);

curNode = tmpNode;
}
}

void main(){
freopen("input.txt", "r", stdin);
int N;
cin >> N;

for(int i = 0; i < N; i++){
cin >> data[i];
cout << data[i] << " " ;
}
cout << endl;

listInit();
ListNode * dstNode = NIL;
for(int i = 0; i < N; i++){
ListNode * node = getNewNode();
node->key = data[i];

listInsertAfter(dstNode, node);
dstNode = dstNode->next;
}

ListNode * curNode = NIL->next;
while(curNode != NIL){
cout << curNode->key << " ";
curNode = curNode->next;
}
cout << endl;

insertSort(data, N);
showData(N);

listInsertSort();
showList();
}