本文已經過時, 最新文章請點擊 : 《【資料結構-重構】連結串列》
循环链表比起单链表增加了最后一个元素的 next 指针域的指向, 那么双向链表就是在循环链表的基础上增加多一个指针域 - previous, 这个指针域指向当前元素之前的那一个元素. 如果当前元素就是 first, 那么这个指针域就会指向最后一个元素
这里用不带 last 指针的 SVG 图表示
上图非常清晰的指明了每一个指针应该指向的位置
在写代码的时候, 没有考虑到直接继承循环链表的类. 但是实际在写的过程中, 除了初始化、清空、摧毁、插入和删除之外, 其他和循环链表的代码其实是基本差不多的
下面给出源代码, 有错误欢迎指出
分成三个文件, 其中一个是 Class 源文件, 分为 .hpp 文件和 .cpp 文件, 另外一个是 main 函数文件
DoubleLinkedList.hpp :
#ifndef DOUBLELINKEDLIST_DOUBLELINKEDLIST_HPP
#define DOUBLELINKEDLIST_DOUBLELINKEDLIST_HPP
#include <iostream>
#include <cstdlib>
namespace DoubleLinkList {
using std::cout;
using std::cin;
using std::endl;
class Node {
protected :
int data;
Node *next;
Node *previous;
public :
int getData();
Node *getNext();
Node *getPrevious();
void insertData(int data);
void insertNext(Node *next);
void insertPrevious(Node *previous);
};
class LinkList : protected Node{
protected :
Node *first;
bool isEmpty();
bool deleteFind(int data);
void deleteOneByElement(int data);
public :
LinkList();
~LinkList();
int getLength();
long long int getElement(int position);
void insert(int data, int position);
void insertFromHead(int data);
void insertFromTail(int data);
int locateElement(int data);
int *locateAllData(int data);
void deleteByPosition(int position);
void deleteByElement(int data);
void cleanList();
void showList();
};
}
#endif //DOUBLELINKEDLIST_DOUBLELINKEDLIST_HPPDoubleLinkedList.cpp :
#include "DoubleLinkedList.hpp"
using namespace DoubleLinkList;
Node *Node::getNext() {
return this->next;
}
Node *Node::getPrevious() {
return this->previous;
}
int Node::getData() {
return this->data;
}
void Node::insertNext(Node *next) {
this->next = next;
}
void Node::insertData(int data) {
this->data = data;
}
void Node::insertPrevious(Node *previous) {
this->previous = previous;
}
LinkList::LinkList() {
first = new Node;
next = first;
previous = first;
first->insertNext(first);
}
LinkList::~LinkList() {
Node *linkList = first->getNext();
while(linkList != first) {
Node *node = linkList;
linkList = node->getNext();
delete node;
}
delete linkList;
}
bool LinkList::isEmpty() {
if(first->getNext() == first) {
return true;
}
return false;
}
int LinkList::getLength() {
if(isEmpty()) {
return 0;
}
Node *linkList = first;
int length = 0;
while(linkList->getNext() != first) {
linkList = linkList->getNext();
length++;
}
return length;
}
long long int LinkList::getElement(int position) {
if(position < 1 || position > getLength()) {
return INT64_MIN;
}
Node *linkList = first;
for(int i = 1; i <= position; i++) {
linkList = linkList->getNext();
}
auto returnData = (long long int)linkList->getData();
linkList = nullptr;
delete linkList;
return returnData;
}
void LinkList::insert(int data, int position) {
if(position < 1 || position > getLength() + 1) {
cout << "Errant position!" << endl;
cout << "Press any key to continue!" << endl;
getchar();
getchar();
return;
}
Node *linkList = first;
auto *newNode = new Node;
newNode->insertData(data);
for(int i = 1; i < position; i++) {
linkList = linkList->getNext();
}
if(position == getLength() + 1) {
newNode->insertNext(first);
newNode->insertPrevious(linkList);
linkList->insertNext(newNode);
first->insertPrevious(newNode);
}else {
newNode->insertPrevious(linkList);
newNode->insertNext(linkList->getNext());
linkList->insertNext(newNode);
}
}
void LinkList::insertFromHead(int data) {
auto *newNode = new Node;
newNode->insertData(data);
newNode->insertNext(first->getNext());
newNode->insertPrevious(first);
first->insertNext(newNode);
}
void LinkList::insertFromTail(int data) {
auto *newNode = new Node;
newNode->insertData(data);
newNode->insertNext(first);
first->insertPrevious(newNode);
Node *linkList = first;
int length = getLength();
for(int i = 1; i <= length; i++) {
linkList = linkList->getNext();
}
linkList->insertNext(newNode);
}
int LinkList::locateElement(int data) {
int position = 0;
Node *linkList = first;
while(linkList->getNext() != first) {
linkList = linkList->getNext();
position++;
if(linkList->getData() == data) {
return position;
}
}
return 0;
};
int *LinkList::locateAllData(int data) {
int count = 0;
Node *linkList = first;
while(linkList->getNext() != first) {
linkList = linkList->getNext();
if(linkList->getData() == data) {
count++;
}
}
if(!count) {
linkList = nullptr;
delete linkList;
return nullptr;
}
auto *returnArray = new int[count + 1];
returnArray[0] = count;
count = 1;
linkList = first;
int length = getLength();
for(int i = 1; i <= length; i++) {
linkList = linkList->getNext();
if(linkList->getData() == data) {
returnArray[count] = i;
count++;
}
}
linkList = nullptr;
delete linkList;
return returnArray;
}
void LinkList::deleteByPosition(int position) {
if(position < 1 || position > getLength()) {
cout << "Errant position!" << endl;
cout << "Press any key to continue!" << endl;
getchar();
getchar();
return;
}
Node *linkList = first;
for(int i = 1; i < position; i++) {
linkList = linkList->getNext();
}
Node *node = linkList->getNext();
if(node->getNext() != first) {
node->getNext()->insertPrevious(linkList);
linkList->insertNext(node->getNext());
delete node;
}else {
linkList->insertNext(first);
first->insertPrevious(linkList);
delete node;
}
}
bool LinkList::deleteFind(int data) {
Node *linkList =first;
while(linkList->getNext() != first) {
linkList = linkList->getNext();
if(linkList->getData() == data) {
return true;
}
}
linkList = nullptr;
delete linkList;
return false;
}
void LinkList::deleteOneByElement(int data) {
Node *linkList = first;
while(linkList->getNext() != first) {
Node *node;
if(linkList->getNext()->getData() == data) {
node = linkList->getNext();
if(node->getNext() == first) {
linkList->insertNext(first);
first->insertPrevious(linkList);
delete node;
}else {
linkList->insertNext(node->getNext());
node->getNext()->insertPrevious(linkList);
delete node;
}
linkList = nullptr;
delete linkList;
break;
}
linkList = linkList->getNext();
}
}
void LinkList::deleteByElement(int data) {
if(deleteFind(data)) {
do {
deleteOneByElement(data);
}while(deleteFind(data));
}else {
cout << "Cannot find the element you entered!" << endl;
cout << "Press any key to continue!" << endl;
getchar();
getchar();
}
}
void LinkList::cleanList() {
Node *linkList = first->getNext();
while(linkList != first) {
Node *node = linkList;
linkList = linkList->getNext();
delete node;
}
first->insertNext(first);
first->insertPrevious(first);
}
void LinkList::showList() {
int length = getLength();
Node *linkList = first;
cout << "Index : \t";
for(int i = 1; i <= length; i++) {
cout << i << "\t";
}
cout << endl << "Element : \t";
while(linkList->getNext() != first) {
linkList = linkList->getNext();
cout << linkList->getData() << "\t";
}
cout << endl;
}main.cpp :
#include "DoubleLinkedList.hpp"
using namespace DoubleLinkList;
void menu();
int main(int argc, char *argv[]) {
auto *linkList = new LinkList();
int choice;
int length;
long long int gottenData;
int location;
int *locationAll;
int data, position;
do {
system("clear");
if(linkList->getLength()) {
linkList->showList();
}
menu();
cin >> choice;
switch(choice) {
case 1 :
length = linkList->getLength();
cout << "The length of the list : " << length << endl;
cout << "Press any key to continue!" << endl;
getchar();
getchar();
break;
case 2 :
cout << "Please enter the position which you want to get its element : ";
cin >> position;
gottenData = linkList->getElement(position);
if(gottenData == INT64_MIN) {
cout << "Cannot find the element you entered!" << endl;
}else {
cout << "Position : " << gottenData << endl;
}
cout << "Press any key to continue!" << endl;
getchar();
getchar();
break;
case 3 :
cout << "Please enter the element's position you want to insert : ";
cin >> position;
cout << "Please enter the element you want to insert : ";
cin >> data;
linkList->insert(data, position);
break;
case 4 :
cout << "Please enter the element you want to insert : ";
cin >> data;
linkList->insertFromHead(data);
break;
case 5 :
cout << "Please enter the element you want to insert : ";
cin >> data;
linkList->insertFromTail(data);
break;
case 6 :
cout << "Please enter the element you want to locate : ";
cin >> data;
location = linkList->locateElement(data);
if(location) {
cout << "Location : \t" << location << endl;
}else {
cout << "Cannot find the element you entered!" << endl;
}
cout << "Press any key to continue!" << endl;
getchar();
getchar();
break;
case 7 :
cout << "Please enter the element you want to locate : ";
cin >> data;
locationAll = linkList->locateAllData(data);
if(locationAll) {
cout << "Location : \t";
for(int i = 1; i <= locationAll[0]; i++) {
cout << locationAll[i] << "\t";
}
cout << endl;
}else {
cout << "Cannot find the element you entered!" << endl;
}
cout << "Press any key to continue!" << endl;
getchar();
getchar();
break;
case 8 :
cout << "Please enter the position you want to delete : ";
cin >> position;
linkList->deleteByPosition(position);
break;
case 9 :
cout << "Please enter the element you want to delete : ";
cin >> data;
linkList->deleteByElement(data);
break;
case 10 :
linkList->cleanList();
break;
case 11 :
delete locationAll;
delete linkList;
exit(0);
default :
break;
}
}while(choice != 11);
}
void menu() {
cout << "1. Get the list's length." << endl;
cout << "2. Get element from the list." << endl;
cout << "3. Insert to the list." << endl;
cout << "4. Insert from head to the list." << endl;
cout << "5. Insert from tail to the list." << endl;
cout << "6. Locate a element from the list." << endl;
cout << "7. Locate all elements from the list." << endl;
cout << "8. Delete elements from the list by position." << endl;
cout << "9. Delete elements from the list by element." << endl;
cout << "10. Clean the list." << endl;
cout << "11. Exit." << endl;
cout << "----------------------------------------------------" << endl;
cout << "Please enter your choice : ";
}自創文章, 原著 : Jonny, 如若需要轉發, 在已經授權的情況下請註明出處 :《数据结构 : 双向链表》https://jonny.vip/2017/12/31/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-%e5%8f%8c%e5%90%91%e9%93%be%e8%a1%a8/
AliPay QR Code
WeChat QR Code
Leave a Reply