前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构:带头结点双向链表的实现(考研)

数据结构:带头结点双向链表的实现(考研)

作者头像
lexingsen
发布2022-02-24 19:10:37
2420
发布2022-02-24 19:10:37
举报
文章被收录于专栏:乐行僧的博客乐行僧的博客
代码语言:javascript
复制
#include <bits/stdc++.h>
using namespace std;


class DoubleLinkedList {
private:
	struct node {
		int val;
		node *next, *prior;
		
		
		node() {}
		node(int x) {
			this->val = x;
		} 
	};
	
	node *head;
	int size;
	
public:
	DoubleLinkedList() {
		head = new node();
		head->next = head->prior = NULL;
		size = 0;
	}
	~DoubleLinkedList() {
		while (head->next!=NULL && head->prior!=NULL) {
			delTail();
		}
		delete head;
	}
	
	
	void insert(int index, int x) {
		if (index<0 || index>size) {
			cout << "the index is invalid!" << endl;
			return;
		}
		
		node *p = head;
		for (int i=0; i<index; ++i) p = p->next;
		/*
		node *q = new node(q)
		q->next = p->next;  p->next可能是NULL指针 
		*/ 
		node *q = new node(x);
		q->next = p->next;
		if (p->next) p->next->prior = q;
		q->prior = p;
		p->next = q;
		
		size ++;
	}
	void insertHead(int x) {insert(0, x);}
	void insertTail(int x) {insert(size, x);}
	
	int del(int index) {
		if (index<0 || index>=size) {
			cout << "the index is invalid!" << endl;
			return -1;
		}
		
		if (head->next==NULL && head->prior==NULL) {
			cout << "the DoubleLinkedList is null!" << endl;
			return -1;
		}
		
		node *p = head;
		for (int i=0; i<index; ++i) p = p->next;
		node *del = p->next;
		int res = del->val;
		if (del->next) {
			del->next->prior = p;
			p->next = del->next; 
			delete del;
		} else {
			p->next = NULL;
			delete del;
		}
		size --;
		return res;
	}
	int delHead() {del(0);}
	int delTail() {del(size-1);}
	
	int get(int index) {
		if (index<0 || index>=size) {
			cout << "the index is invalid!" << endl;
			return -1;
		}
		
		if (head->next==NULL && head->prior==NULL) {
			cout << "the DoubleLinkedList is null!" << endl;
			return -1;
		}
		
		node *p = head->next;
		for (int i=0; i<index; ++i) p = p->next;
		return p->val;
	}
	int getHead() {return get(0);}
	int getTail() {return get(size-1);}
	
	void show() {
		node *p = head->next;
		while (p) {
			cout << p->val << " ";
			p = p->next;
		} 
		cout << endl;
	}
	
	bool isEmpty() {
		return head->next==NULL && head->prior==NULL;
	}
}; 

int main() {
	int a[] = {1,2,3,4,5};
	int n = sizeof(a)/sizeof(int);
	DoubleLinkedList l = DoubleLinkedList();
	for (int i=0; i<n; ++i) l.insertTail(a[i]);
	l.show();
	
	l.delHead();
	l.show();
	l.delTail();
	l.show();
	cout << l.getHead() << endl;
	cout << l.getTail() << endl;
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档