C++实现双向链表(List)

list是C++容器类中的“顺序存储结构”所包含的一种结构。list是非连续存储结构,具有双链表结构,支持前向/后向遍历,且支持高效的随机删除/插入。

实现代码如下:

**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){//插在头结点之后
  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位置前插入数据
  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;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • c++双向链表操作示例(创建双向链、双向链表中查找数据、插入数据等)

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. (1)定义双向链表的基本结构 复制代码 代码如下: typedef struct _DOUBLE_LINK_NODE  {      int data;      struct _DOUBLE_LINK_NODE* prev;      struct _DOUBLE_LINK_NODE* nex

  • C++ 实现双向链表的实例

    双向链表C++ 的实现 本文是通过C++ 的知识实现数据结构中的双向链表,这里不多说 了,代码注释很清楚, 实现代码: //double LinkList implement with C++ template #include<iostream> using namespace std; /*template<typename Type> class DBListADT { public: virtual void Append(const Type &)=0; virt

  • C++ STL入门教程(2) list双向链表使用方法(附程序代码)

    一.简介 "Unlike other standard sequence containers, list and forward_list objects are specifically designed to be efficient inserting and removing elements in any position, even in the middle of the sequence." Lists将元素按顺序储存在链表中.与向量(vector)相比, 它允许快速

  • 深入解析C++的循环链表与双向链表设计的API实现

    循环链表设计与API实现 基本概念 循环链表的定义:将单链表中最后一个数据元素的next指针指向第一个元素 循环链表拥有单链表的所有操作 创建链表 销毁链表 获取链表长度 清空链表 获取第pos个元素操作 插入元素到位置pos 删除位置pos处的元素 新增功能:游标的定义 在循环链表中可以定义一个"当前"指针,这个指针通常称为游标,可以通过这个游标来遍历链表中的所有元素. 循环链表新操作 将游标重置指向链表中的第一个数据元素 CircleListNode* CircleList_Res

  • 关于双向链表的增删改查和排序的C++实现

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 由于双向链表可以方便地实现正序和逆序两个方向的插入.查找等功能,在很多算法中经常被使用, 这里用C++构造了一个双向链表,提供了对双向链表的插入.查找.删除节点.排序等功能,其中排序提供了插入排序和冒泡排序两种方式 #include<iostream> using namespace std;

  • C++ 构造双向链表的实现代码

    构造双向链表,不足之处,还望指正!  复制代码 代码如下: // DoubleLinkedList.cpp : 定义控制台应用程序的入口点.//构造双向链表,实现从控制台输入,插入,删除,求大小size等操作#include "stdafx.h"#include <iostream>using namespace std;//定义双向链表的节点template<class T>struct NODE{ NODE<T>* pre; T data; NO

  • C++ 模版双向链表的实现详解

    代码如下所示: 复制代码 代码如下: #include <iostream>template <typename T>class double_linked{    struct node    {        T data;        node* prev;        node* next;        node(T t, node* p, node* n) : data(t), prev(p), next(n) {}    };    node* head;   

  • C++实现双向链表

    本文实例为大家分享了C++实现动态顺序表的具体代码,供大家参考,具体内容如下 List.h #pragma once #include <stdio.h> #include <iostream> #include <assert.h> using namespace std; typedef int DataType; struct ListNode { ListNode* _next; //存放下一个节点地址 ListNode* _prev; //存放上一个节点地址

  • C++将二叉树转为双向链表及判断两个链表是否相交

    把二叉查找树转变成排序的双向链表 例如: 转换成双向链表 4=6=8=10=12=14=16 struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 首先阐述下二叉排序树: 它首先要是一棵二元树,在这基础上它或者是一棵空树:或者是具有下列性质的二元树: (1)若左子树不空

  • Python二叉搜索树与双向链表转换实现方法

    本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.

  • java中使用双向链表实现贪吃蛇程序源码分享

    使用双向链表实现贪吃蛇程序 1.链表节点定义: package snake; public class SnakeNode { private int x; private int y; private SnakeNode next; private SnakeNode ahead; public SnakeNode() { } public SnakeNode(int x, int y) { super(); this.x = x; this.y = y; } public int getX(

  • Java中双向链表详解及实例

    Java中双向链表详解及实例 写在前面: 双向链表是一种对称结构,它克服了单链表上指针单向性的缺点,其中每一个节点即可向前引用,也可向后引用,这样可以更方便的插入.删除数据元素. 由于双向链表需要同时维护两个方向的指针,因此添加节点.删除节点时指针维护成本更大:但双向链表具有两个方向的指针,因此可以向两个方向搜索节点,因此双向链表在搜索节点.删除指定索引处节点时具有较好的性能. Java语言实现双向链表: package com.ietree.basic.datastructure.dublin

  • Java实现双向链表(两个版本)

    临近春节,项目都结束了,都等着回家过年了.下面是小编给大家研究数据结构的相关知识,链表算是经常用到的一种数据结构了,现将自己的实现展示如下,欢迎大神赐教. 第一个版本,没有最后一个节点,每次从根节点开始遍历 public class LinkedList<E> { private Node head; public LinkedList() { } public E getFirst(){ if(head==null){ return null; } return head.value; }

  • python双向链表实现实例代码

    示意图: python双向链表实现代码: 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class Node(object):    def __init__(self,val,p=0):        self.data = val        self.next = p        self.prev = p class LinkList(object):    def __init__(self):        self.he

  • C#数据结构与算法揭秘四 双向链表

    首先,明白什么是双向链表.所谓双向链表是如果希望找直接前驱结点和直接后继结点的时间复杂度都是 O(1),那么,需要在结点中设两个引用域,一个保存直接前驱结点的地址,叫 prev,一个直接后继结点的地址,叫 next,这样的链表就是双向链表(Doubly Linked List).双向链表的结点结构示意图如图所示. 双向链表结点的定义与单链表的结点的定义很相似, ,只是双向链表多了一个字段 prev.其实,双向链表更像是一根链条一样,你连我,我连你,不清楚,请看图. 双向链表结点类的实现如下所示

  • C#双向链表LinkedList排序实现方法

    本文实例讲述了C#双向链表LinkedList排序实现方法.分享给大家供大家参考.具体如下: 1.函数 打印链表函数PrintLinkedList 和 排序函数SortLinkedList 注:下面代码中的链表每项都是double类型,如果换做其他的类型或结构,则需要适当修改 /// <summary> /// 打印链表各结点信息 /// </summary> /// <param name="ll"></param> private s

  • C语言之双向链表详解及实例代码

    1,双向链表简介. 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 2,例子要求: 完成双向链表的插入.删除以及查找,将学生管理系统使用的数组,以双向链表的方式实现,能够支持无限制的学生人数的增删改查以及保存. 3,代码实现. #include <stdio.h> #include <string.h> #include <

  • PHP小教程之实现双向链表

    看了很久数据结构但是没有怎么用过,在网上看到了关于PHP的数据结构,学习了一下,与大家一起分享一下.上一次分享了<PHP小教程之实现链表>,这次来补充说一下双向链表. 复制代码 代码如下: <?php        class Hero        {            public $pre=null;            public $no;            public $name;            public $next=null;           

随机推荐