对最后一个链接点的引用允许项在表头一样，在表尾直接插入一个链接点。当然，仍然可以在普通的单链表的表尾插入一个链接带你，方法是遍历整个链表直到直达表尾，但是这种方法效率很低
像访问表头一样访问表尾的特性，使双端链表更适合于一些普通链表不方便 *** 作的场合，比如频繁要插入队尾元素的场合
双端链表的示例程序
这个程序在表头和表尾各插入三个连点，显示插入后的链表。然后删除头两个链接点，再次显示
表头在重复插入 *** 作会颠倒链接点进入的顺序，而在表尾重复插入则保持链接点进入的顺序
双端链表有两个项，first和last，一个指向链表中的第一个链接点，另一个指向最后一个链接点。如果链表中只有一个链接点，first和last都指向它，如果没有链接点，两者都为null值
插入和删除方法和普通链表的相应部分类似。然而，两个插入方法都要考虑一种特殊情况，即插入前链表是空的，如果isEmpty（）是真，那么insertFirst必须把last指向新的链接点，insertLast也必须把first指向新的链接点
如果用insertFirst （）方法实现在表头插入，first就指向新的链接点，用insertLast()方法实现在表尾插入，last就指向新的链接点。如果链表只有一个链接点，那么从表头删除也是一种特殊情况，last必须被赋值为null值
不幸的是，用双端链表也不能有助于删除最后一个链接点，因为没有一个引用指向倒数第二个链接点，如果最后一个链接点被删除，倒数第二个链接点的next字段应该变成null值，为了删除最后一个链接点，需要一个双向链表，下篇会讨论它
在表头插入和删除速度很快，仅需要改变一两个引用值，所以花费O(1)的时间
平均起来，查找，删除和在指定链接点后面插入都需要搜索链表中一半链接点。需要O(N)此比较，在数组中执行这些 *** 作也需要O(N)次比较，但是链表仍然要快一些，因为当插入和删除链接点时，链表不需要移动任何东西，增加的效率是很明显的，特别是当复制时间远远大于比较时间的时候
当然，链表比数组优越的另外一个重要方面是链表需要多少内存就可以用多少内存，冰倩可以扩展到所有可用内存。数组的大小在它创建的时候就固定了；所以经常由于数组太大导致效率低下，或者数组太小导致空间溢出。向量是一种可扩展的数组，它可以通过可变长度解决这个问题，但是它经常只允许以固定大小的增量扩展（例如快要溢出的时候，就增加一倍数组容量），这个解决方案在内存使用效率上来说还是比链表的低
#include <iostream>#include <string>
using namespace std
template <class T>
struct ListNode
{
T value
struct ListNode<T>*next
struct ListNode<T>*prior
}
template <class T>
class List
{
private:
struct ListNode<T>*head
int length
public:
List()
{
head = new ListNode<T>
head->next = NULL
head->prior = NULL
length = 0
}
~List(){}
void Push_Front(T value)//从前添加元素
void Push_Back(T value)//从后添加元素
T operator[] (int index)//输出单个元素
void Delete(int index)//删除元素
void Display()//遍历元素
}
template <class T>
void List<T>::Display()
{
struct ListNode<T>*node = head
while (node->next != NULL)
{
node = node->next
cout<<node->value<<" "
}
}
template <class T>
void List<T>::Push_Front(T value)
{
struct ListNode<T>*node = new ListNode<T>
node->value = value
node->next = head->next
head->next = node
node->prior = head
length++
}
template <class T>
void List<T>::Push_Back(T value)
{
struct ListNode<T>*last_node = head
while (last_node->next != NULL)
{
last_node = last_node->next
}
struct ListNode<T>*node = new ListNode<T>
node->value = value
node->next = last_node->next
last_node->next = node
node->prior = last_node
length++
}
template <class T>
void List<T>::Delete(int index)
{
struct ListNode<T>*front_node = head, *curr_node = head->next
for (int i = 0i <index-1i++)
{
front_node = front_node->next
curr_node = curr_node->next
}
curr_node->next->prior = front_node
front_node->next = curr_node->next
delete curr_node
length--
}
template <class T>
T List<T>::operator[] (int index)
{
struct ListNode<T>*node = head
for (int i = 0i <indexi++)
{
node = node->next
}
return node->value
}
void main()
{
List<int>L
int value
while (cin>>value &&value != 0)
{
L.Push_Front(value)
}
L.Delete(3)
L.Display()
cout<<L[3]<<endl
}
#include <iostream>using namespace std
class Node {
public:
int element
Node *next
Node *previous
Node(int element, Node *next, Node *previous) {
this->element = element
this->next = next
this->previous = previous
}
}
class LinkedList {
LinkedList()
void addFirst(int)
void addLast(int)
void add(int index, int element)
int getFirst()
int getLast()
int get(int)
int removeFirst()
int removeLast()
int remove(int)
void iterate()
private:
Node *header
int size
}
/*
* 构造方法。
* 生成一个空的节点介于表头和表尾之间，初始前后指针都指向自己。
*/
LinkedList::LinkedList() {
header = new Node(NULL, NULL, NULL)
header->next = header
header->previous = header
size = 0
}
/*
* 在链表头部添加一个元素。
* 生成一个新的节点，向前指向空节点，向后指向原来空节点的下一个节点，即原来的第一个节点。
* 空节点向后指向此节点，原来的第一个节点向前指向此节点。
*/
void LinkedList::addFirst(int i) {
header->next = new Node(i, header->next, header)
header->next->next->previous = header->next
++size
}
/*
* 在链表最后添加一个元素。
* 生成一个新的节点，向前指向原来空节点的前一个节点，即原来的最后一个节点，向后指向空节点。
* 原来的最后一个节点向后指向此节点，空节点向前指向此节点。
*/
void LinkedList::addLast(int i) {
header->previous = new Node(i, header, header->previous)
header->previous->previous->next = header->previous
++size
}
/*
* 在指定的索引前插入一个元素。0 <= 索引 <= 链表长度。
* 如果索引值小于链表长度的一半，向后（正向）迭代获取索引值位置的节点，反之则向前（反向）。
* 生成一个新的节点，向前指向原来这个位置的节点的前一个节点，向后指向原来这个位置的节点。
* 原来这个位置的节点的前一个节点向后指向此节点，原来这个位置的节点向前指向此节点。
* （在指定的索引删除一个元素实现方法类似）
*/
void LinkedList::add(int index, int i) {
if(index >size || index <0) {
cout <<"Exception in add(): Index out of bound." <<'\n'
return
}
Node *entry
if(index <size / 2) {
entry = header->next
for(int i = 0i <index++i)
entry = entry->next
}
else {
entry = header
for(int i = sizei >index--i)
entry = entry->previous
}
entry->previous->next = new Node(i, entry, entry->previous)
entry->previous = entry->previous->next
++size
}
/*
* 获取链表第一个元素。
* 空节点向后指向的节点即是第一个元素。
*/
int LinkedList::getFirst() {
if(!size)
cout <<"Exception in getFirst(): List is empty." <<'\n'
return header->next->element
}
/*
* 获取链表最后一个元素。
* 空节点向前指向的节点即是最后一个元素。
*/
int LinkedList::getLast() {
if(!size)
cout <<"Exception in getLast(): List is empty." <<'\n'
return header->previous->element
}
/*
* 删除并返回链表第一个元素。
* 链表第二个节点向前指向空节点，空节点向后指向第二个节点。
*/
int LinkedList::removeFirst() {
int remove = header->next->element
header->next->next->previous = header
header->next = header->next->next
--size
return remove
}
/*
* 删除并返回链表最后一个元素。
* 链表倒数第二个节点向后指向空节点，空节点向前指向倒数第二个节点。
*/
int LinkedList::removeLast() {
int remove = header->previous->element
header->previous->previous->next = header
header->previous = header->previous->previous
--size
return remove
}
/*
* 用来输出所有元素的迭代方法。
*/
void LinkedList::iterate() {
if(!size) {
cout <<"Exception in iterate(): List is empty." <<'\n'
return
}
for(Node *entry = header->nextentry != headerentry = entry->next)
cout <<entry->element <<" "
cout <<'\n'
}
int main()
{
cout <<"Hello World!" <<endl
return 0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）