C++實現(xiàn)雙向鏈表（List）

更新時間：2020年05月25日 09:23:14 作者：get_it_started

這篇文章主要為大家詳細介紹了C++實現(xiàn)雙向鏈表，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

list是C++容器類中的“順序存儲結(jié)構(gòu)”所包含的一種結(jié)構(gòu)。list是非連續(xù)存儲結(jié)構(gòu)，具有雙鏈表結(jié)構(gòu)，支持前向/后向遍歷，且支持高效的隨機刪除/插入。

實現(xiàn)代碼如下：

**list.h**

#pragma once

#include<stdio.h>
#include<assert.h>
#include<iostream>
using namespace std;

typedef int DataType;

struct ListNode
{
 ListNode* _next;
 ListNode* _prev;

 DataType _data;

 ListNode(DataType x)
  :_data(x)
  , _next(NULL)
  , _prev(NULL)
 {}
};

**test.cpp**

#define _CRT_SECURE_NO_WARNINGS 1

#include "list.h"

class List{
 typedef ListNode Node;
public:
 List()
  :_head(new Node(DataType())){
  _head->_next = _head;
  _head->_prev = _head;
 }

 List(const List& l)
  :_head(new Node(DataType())){
  _head->_next = _head;
  _head->_prev = _head;
  Node* cur = l._head->_next;
  while (cur!=l._head){
   PushBack(cur->_data);
   cur = cur->_next;
  }
 }

 List& operator=(const List& l){
  if (this != &l){
   //swap(_head, l._head);
  }
  return *this;
 }

 ~List(){
  Node* cur = _head->_next;
  while (cur != _head){
   Node* next= cur->_next;
   delete cur;
   cur = next;
  }
  delete _head;
  _head = NULL;
 }

 void PushBack(DataType x){
  Node* prev = _head->_prev;
  Node* new_node = new Node(x);
  prev->_next = new_node;
  new_node->_prev = prev;
  _head->_prev = new_node;
  new_node->_next = _head;
 }

 void PushFront(DataType x){//插在頭結(jié)點之后
  Node* cur = _head->_next;
  Node* new_node = new Node(x);
  new_node->_next = cur;
  cur->_prev = new_node;
  new_node->_prev = _head;
  _head->_next = new_node;
 }

 void PopBack(){
  Node* delete_node = _head->_prev;
  Node* cur = delete_node->_prev;
  _head->_prev = cur;
  cur->_next = _head;
  delete delete_node;
 }

 void PopFront(){
  Node* delete_node = _head->_next;
  Node* cur = delete_node->_next;

  _head->_next = cur;
  cur->_prev = _head;
  delete delete_node;
 }

 Node* Find(DataType x){
  Node* to_find = _head->_next;
  while (to_find != _head){
   if (to_find->_data == x){
    return to_find;
   }
   to_find = to_find->_next;
  }
  return NULL;
 }

 void Insert(Node* pos, DataType x){//在pos位置前插入數(shù)據(jù)
  assert(pos);
  Node* new_node = new Node(x);
  Node* prev = pos->_prev;
  new_node->_next = pos;
  pos->_prev = new_node;
  new_node->_prev = prev;
  prev->_next = new_node;
 }

 void Erase(Node* pos){
  assert(pos);
  Node* prev = pos->_prev;
  Node* next = pos->_next;
  prev->_next = next;
  next->_prev = prev;
  delete pos;
 }

 void Print() const{
  Node* cur = _head->_next;
  cout <<" _head->";
  while (cur!= _head){
   cout << cur->_data << "->";
   cur = cur->_next;
  }
  cout << endl;
  Node* pos = _head->_prev;
  while (pos != _head){
   cout << pos->_data << "<-";
   pos = pos->_prev;
  }
  cout << "_head" << endl;
 }
private:
 Node* _head;
};

void TestList(){
 List L;
 L.PushBack(1);
 L.PushBack(2);
 L.PushBack(4);
 L.PushBack(5);
 L.PopBack();
 L.Print();

 ListNode* pos = L.Find(1); 
 printf("pos->data：%d[%p]\n",pos->_data,pos);
 pos = L.Find(2);
 printf("pos->data：%d[%p]\n", pos->_data, pos);
 pos = L.Find(4);
 printf("pos->data：%d[%p]\n", pos->_data, pos);
 printf("\n");

 L.Insert(pos, 3);
 L.Print();
 L.Erase(pos);
 L.Print();
 printf("\n");

 List L1;
 L1.PushFront(4);
 L1.PushFront(3);
 L1.PushFront(2);
 L1.PushFront(1);
 L1.Print();
 L1.PopFront();
 L1.Print();

}

int main(){
 TestList();
 return 0;
}

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: