# 数据结构面试之二——双向链表表、循环链表、有序链表的常见操作

## 二、双向链表

### 1.双向链表的构建【前面插入】

//反向表头插入，从前面插入...

template<typename Type>
{
nodeType<Type> *newNode;

int num;
cout << " Enter a list of integer end with -999." << endl;
cin >> num;

while(num != -999)
{
newNode = new nodeType<Type>;
newNode->info = num;
newNode->next = NULL;
newNode->back = NULL;

if(first == NULL)
{
first = newNode;
}
else
{
newNode->next = first;
first->back = newNode;
first = newNode;
}

cin >> num;
}
return first;
}

### 2.双向链表的插入节点【此处考虑插入后保证有序，直接插入排序】

1）双向链表为空，“提示信息”并返回。

2）双向链表非空，待插入节点的元素值小于first节点，需要修改first指针。

3）双向链表非空，待插入节点的元素值为链表中间的节点，需修改back、next指向。

4）双向链表非空，待插入节点在最末尾节点以后，修改最末节点的指针。

//双向不循环链表
template<typename Type>
{
nodeType<Type> *current;
nodeType<Type> *trailCurrent;
nodeType<Type> *newNode;
bool found = false;

newNode = new nodeType<Type>;
newNode->info = insertItem;
newNode->next = NULL;
newNode->back = NULL;

//case 1: 空表
if(first == NULL)
{
first = newNode;
}
else
{
current = first;
while( current != NULL)
{
if( current->info >= insertItem )
{
found = true;
break;
}
else
{
trailCurrent = current;
current = current->next;
}
}

//case 2: 第一个节点
if(current == first)
{
current->next = newNode;
newNode->back = current;
}
else
{
//case 3: 中间节点
if(current != NULL)
{
newNode->next = trailCurrent->next;
current->back = newNode;
trailCurrent->next = newNode;
newNode->back = trailCurrent;
}
else  //case 4:最后一个节点前
{
trailCurrent->next = newNode;
newNode->back = trailCurrent;
}//end case 4
}
}
}

### 3.双向链表的删除节点

1） 链表为空，“提示信息”并返回。

2） 链表非空，查找删除的元素在链表是否存在。是的话，found=true；否的话，found=false。

3） 如果没有找到包含查找元素的节点，“错误提示”并返回。

4） 如果找到，主要节点位置。如果是头节点或末尾节点主要修改first指针，及节点的back、next指向；如果不是头节点或者末尾节点就是中间节点，主要back、next的指向，完成插入。

template<typename Type>
{
nodeType<Type> *current = new nodeType<Type>;
nodeType<Type> *trailCurrent;
bool found = false;

//case 1: 空表
if(first == NULL)
{
cout << "The List is NULL!" << endl;
exit(1);
}
else
{
current = first;
while( current != NULL)
{
if( current->info == deleteItem )
{
found = true;
break;
}
else
{
trailCurrent = current;
current = current->next;
}
}

if(found)
{
//case 2: 第一个节点
if(current == first)
{
first = current->next;
delete current;
}
else
{
//case 3: 中间节点
if(current != NULL)
{
if(current->next != NULL)  //case3.1:要删除的是中间节点.
{
trailCurrent->next =current->next;
current->next->back = trailCurrent;
delete current;
}
else
{
trailCurrent->next = NULL;//case3.2:要删除的为最后一个节点.
delete current;
}
}

}// end else
}// end if
else
{
cout << "The elem " <<deleteItem << " is not Exist in the List!" << endl;//case 4: 链表中无此节点.
}
}//end else
}//end

## 三、循环链表

### 1.前插式构建循环链表

template<typename Type>
void cycleList<Type>::bulidCycListBackward() //前插构造循环链表.
{
Type newItem;
while(cin >> newItem, newItem != -999)
{
nodeType<Type>* newNode = newnodeType<Type>;
newNode->info = newItem;

if(first == NULL)
{
first = newNode;
last = newNode;
}
else
{
first = newNode;
}
}
cout << "输入完毕!" << endl;
}


### 2. 循环链表插入元素[后插入]

//只在last末尾插入
template<typename Type>
voidcycleList<Type>::insertCycList(const Type& newItem)
{
nodeType<Type> *newNode = new nodeType<Type>;
newNode->info = newItem;

if(first == NULL)        //链表为空...
{
first = newNode;
last = newNode;
}
else                   //链表非空...
{
last = newNode;
}
cout << newItem << "was inserted!" <<endl;
}

### 3.删除循环链表节点

//case1:链表为空。
//case2:链表非空，删除节点为头节点。
//case3:链表非空，删除节点为尾节点。
//case4:链表非空，删除节点为中间节点。
//case5:链表非空，不存在=deleteItem的节点。
template<typename Type>
voidcycleList<Type>::delCycList(const Type& deleteItem)
{
nodeType<Type> *current = new nodeType<Type>;
nodeType<Type> *trailCurrent = new nodeType<Type>;
nodeType<Type> *temp ;
bool found = false;

if( first == NULL )
{
cout << "The List is Empty!" << endl;//case1
return;
}
if( first->info == deleteItem )      //case2
{
temp = new nodeType<Type>;
temp = first;
cout << "The node has" << deleteItem<< " was deleted! " << endl;
delete temp;
return;
}
else                                             //cas3,case4.需要查找后定位。
{
while( !found && current != first)
{
if( current->info == deleteItem )
{
found = true;
break;
}
else
{
trailCurrent = current;
}
}// end while

if(found)
{
temp = new nodeType<Type>;
if(current == last)                        //case3
{
temp = last;
last = trailCurrent;
}
else
{
temp = current;
}
cout << "The Elem : " <<deleteItem << " was deleted! " << endl;
delete temp;
}
else
{
cout << "The Elem : " <<deleteItem << " was not Exist in the List! " << endl;
}
}//end else
}

## 四、有序链表

### 1.有序链表的插入

1） 当前链表为空；

2） 当前链表非空，要插入的元素值小于头结点的元素值；

3） 当前链表非空，要插入的元素值大于头结点的元素值，可以考虑找到第一个大于其的元素则停止搜索，插入其前即可。

template<typename Type>
{
nodeType<Type>* current;
nodeType<Type>* trailCurrent;
nodeType<Type>* newNode;

bool found = false;

newNode = new nodeType<Type>;
newNode->info = newItem;

if(first == NULL)                           //case1：链表为空.
{
first = newNode;
last = first;
}
else
{
current = first;
while( !found && current != NULL)       //循环查找
{
if(current->info >= newItem)
{
found = true;
break;
}
else
{
trailCurrent = current;
}
}//end while

//first 特殊处理..
if(current == first)                //case2：新插入的元素小于first节点的元素值..
{
first = newNode;
}
else //其他..
{
}
}//end else
}

### 2.      递归实现有序链表的逆序打印

template<typename Type>
{
reversePrint(first);
cout << endl;
}

//递归实现单链表的逆序打印.
template<typename Type>
{
if(current != NULL)
{
cout << current->info << "\t";
}
}

|
10天前
|

【数据结构】链表从实现到应用，保姆级攻略

31 10
|
28天前
|

【初阶数据结构篇】顺序表和链表算法题

13 0
|
28天前
|

【初阶数据结构篇】双向链表的实现（赋源码）

18 0
|
28天前
|

【初阶数据结构篇】单链表的实现（附源码）

16 0
|
1月前
|

【数据结构与算法】共享双向链表
【数据结构与算法】共享双向链表
10 0
|
1月前
|

【数据结构与算法】双向链表
【数据结构与算法】双向链表
10 0
|
4天前
|

22 8
|
6天前
|

25 3
|
8天前
|
Java
【数据结构】栈和队列的深度探索，从实现到应用详解

11 0
|
1月前

37 1