双向链表 – 数据结构

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表

//节点定义

    struct Node
    {
    	int x;
    	int y;
    	Node* next;
    	Node* pre;
    	Node(int _x,int _y, Node* n=nullptr,Node* p=nullptr)
    	{
    		x = _x;
    		y = _y;
    		next = n;
    		pre = p;
    	}
    	friend ostream& operator<<(ostream& os,Node a)//输出重载
    	{
    		os <<"( "<< a.x << " " << a.y <<" )"<< endl;
    		return os;
    	}
    };


//List类 头文件
class List
{
private:
  Node* head;
  Node* tail;
  int count;
public:
  List();
  ~List();
  void Insert(Node* n,int index);//插入n指向的节点
  void Insert(int x, int y, int index);//重载
  void InsertHead(Node* n);//头插
  void InsertHead(int x, int y);//头插重载
  void Delete(int index);//删除指定位置节点
  void Delete(int x,int y);//删除指定节点
  void DeleteTail();//尾删
  Node* Search_Node(int x, int y);//搜寻指定节点,返回节点
  int Search_In(int x, int y);//搜寻指定节点,返回位置
  Node* Search(int index);//返回指定位置处节点
  void Out();//打印链表
 
};


//构造函数
List::List()
{
  head = nullptr;
  tail = nullptr;
  count = 0;
}
//析构函数
List::~List()
{
  while (head != nullptr)
  {
    Node* q = head->next;
    delete head;
    head = q;
  }
}
//查找
Node* List::Search_Node(int x, int y)
{
  Node* q = head;
  while (q != nullptr && (x != q->x || y != q->y))
  {
    q = q->next;
  }
  return q;//未找到则返回nullptr
}
int List::Search_In(int x, int y)
{
  Node* q = head;
  int i=0;
  while (q != nullptr && (x != q->x || y != q->y))
  {
    q = q->next;
    i++;
  }
  if (q==nullptr)//未找到
  {
    return -1;
  }
  else
    return i;
}
Node* List::Search(int index)
{
  if (index < count / 2)//从左向右
  {
    Node* q = head;
    for (int i = 0; i < index; i++)
    {
      q = q->next;
    }
    return q;
  }
  else//从右向左
  {
    Node* q = tail;
    for (int i = 0; i < count-index-1; i++)
    {
      q = q->pre;
    }
    return q;
  }
}

//插入
void List::Insert(Node* n,int index)//插在第index位置上(位于原index节点之前)
{
  if (index<0 || index>count)//无效索引
  {
    ostringstream s;
    s << "index= " << index << " size = " << count;
    throw s;
  }
  if (index == 0)//头插
  {
    n->pre = nullptr;
    n->next = head;
    head = n;
    if (!n->next)
    {
      tail = n;
    }
    else
    {
      n->next->pre = n;
    }
  }
  else//寻找新节点前驱  进入以下模块则count!=0
  {
    Node* q = head;
    for (int i = 0; i < index-1; i++)//若为i<index则为寻找后继
    {
      q = q->next;
    }
    //在q之后插入
    n->pre = q;
    n->next = q->next;
    q->next = n;
    if (!n->next)//尾指针更新
    {
      tail = n;
    }
    else
    {
      n->next->pre = n;
    }
  }
  count++;
}
void List::Insert(int x, int y, int index)
{
  Node* n = new Node(x, y);
  Insert(n, index);
}
void List::InsertHead(Node* n)
{
  Insert(n, 0);
}
void List::InsertHead(int x, int y)
{
  Insert(x, y, 0);
}

//删除
void List::Delete(int index)
{
  if (index<0 || index>=count)//无效索引(此处为》=)
  {
    ostringstream s;
    s << "index= " << index << " size = " << count;
    throw s;
  }
  Node* d;
  if (index == 0)
  {
    d = head;
    head = head->next;
    if (head == nullptr)
      tail = nullptr;//更新尾指针
    else
    {
      head->pre = nullptr;
    }
  }
  else//寻找前驱  进入以下模块则count!=0
  {
    Node* q = head;
    for (int i = 0; i < index - 1; i++)//若为i<index则为寻找后继
    {
      q = q->next;
    }
    d= q->next;
    q->next = q->next->next;
    if (q->next)
    {
      q->next->pre = q;
    }
    else
    {
      tail = q;
    }
  }
  count--;
}
void List::Delete(int x, int y)
{
  int n = Search_In(x, y);
  Delete(n);
}
void List::DeleteTail()
{
  Delete(count - 1);
}

//打印测试
void List::Out()
{
  cout << head << endl;
  for (Node* q = head; q != nullptr; q = q->next)
  {
    //cout << *q;
    cout << q->pre << "  " << q << "  " << q->next << endl;
  }
  cout << tail << endl;
}


//实现
List L;
  L.Insert(1, 2,0);
  L.Insert(1, 2, 0);
  L.Insert(1, 2, 0);
  L.Insert(1, 2, 0);
  L.Insert(1, 2, 0);
  L.Out();
  cout << endl;
  L.Insert(1, 7, 3);
  L.Out();
  cout << endl;
  L.Insert(11, 11, 5);
  L.Out();
  cout << endl;

单向链表 && 双向链表 区别

单向链表只可向一个方向遍历。

查找一个节点的时候需要从第一个节点开始每次访问下一个节点,一直访问到需要的位置。也可以提前把一个节点的位置另外保存起来,然后直接访问。 双向链表中不仅有指向后一个节点的指针,还有指向前一个节点的指针。第一个节点的”前连接”指向NULL,最后一个节点的”后连接”指向NULL。

这样可以从任何一个节点访问前一个节点,也可以访问后一个节点,以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。

由于另外储存了指向链表内容的指针,并且可能会修改相邻的节点,有的时候第一个节点可能会被删除或者在之前添加一个新的节点。这时候就要修改指向首个节点的指针。

结果:

You may also like...

发表评论

电子邮件地址不会被公开。