# DSLearning_list

**Repository Path**: zyflzz/dslearning_list

## Basic Information

- **Project Name**: DSLearning_list
- **Description**: 数据结构学习——链表部分
- **Primary Language**: Unknown
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-04-19
- **Last Updated**: 2023-04-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# README

## 简介

功能：实现双向环形链表

工程环境：CMake

文件目录介绍：

* 结点类 `Node` 位于 `LinkedList/Node.hpp`
* 链表类 `LinkedList` 位于 `LinkedList/LinkedList.hpp` 
* `CMakeProject_2_List.cpp` 用于测试

## 双向链表简介

该项目实现的双向链表示意图如下

<img src="./README.assets/A01010102双向链表.png" alt="A01010102双向链表" style="zoom:30%;" />

每一个结点都由四个部分组成（这里只画出了三个），包括：数据、`next` 指针、`prev` 指针以及结点类型。

* `next` 指针用来指向下一个结点，`prev` 指针用来指向前一个结点；
* 结点类型包括：头部结点类型（`HEAD`）、尾部结点类型（`TAIL`）、普通结点类型（`NORMAL`），头部结点就是头部结点类型，尾部结点就是尾部结点类型，其他结点就是普通结点类型。这样做是为了方便区分头尾结点和其他结点（节点类型定义为枚举类）。

初始状态有一个头部结点和尾部结点，即 `head` 和 `tail`，这两个结点中没有数据，只有 `prev` 指针和 `next` 指针。头部结点和尾部结点虽然在链表中，但是不计入总长度（因为这不是使用者创建的，而是编码者创建的）。即初始状态时链表长度为 0，当且仅当使用者添加结点后，长度才会大于 0。

初始状态时 `head->next` 指向 `tail`，`tail->prev` 指向 `head`；`head->prev` 指向 `tail`，`tail->next` 指向 `head`。

对于链表的增删操作，具体如下：

**添加结点时**，分为尾部添加和头部添加两种，设新添加的结点为 `newNode`：

* 尾部添加：先获取最后一个结点 `latestNode`，将 `newNode` 的 `prev` 指向 `latestNode`，将 `newNode` 的 `next` 指向 `tail`；将 `latestNode` 的 `next` 指向 `newNode`，将 `tail` 的 `prev` 指向 `newNode`。
* 头部添加：先获取第一个结点 `firstNode`，将 `newNode` 的 `next` 指向 `firstNode`，将 `newNode` 的 `prev` 指向 `head`；将 `firstNode` 的 `prev` 指向 `newNode`，将 `head` 的 `next` 指向 `newNode`。
* 一定要注意设置指针指向的顺序，因为 `latestNode` 是通过 `tail->prev` 获取的，`firstNode` 是通过 `head->next` 获取的。如果在此之前就设置了“将 `tail` 的 `prev` 指向 `newNode`”或“将 `head` 的 `next` 指向 `newNode`”的话，我们获取到的就不是真正的 `latestNode` 和 `firstNode` 了。

**删除结点时**，先锁定要删除的结点，设为 `node`，然后将 `node->prev` 的 `next` 指向 `node->next`，将 `node->next` 的 `prev` 指向 `node->prev`，这样 `node` 就被剥离下来了，达到了删除的效果

对于链表的迭代，主要有 `hasNext,hasPrev` 和 `next,prev` 操作：

* `hasNext` 判断是否有下一个结点（首尾节点不算），只需要判断当前节点的下一个结点类型是否为 `NORMAL`
* `hasPrev` 判断是否有删一个结点（首尾节点不算），只需要判断当前节点的上一个结点类型是否为 `NORMAL`
* `next` 是当前指针指向下一个结点
* `prev` 是当前指针指向上一个结点

## 代码设计思路

设计时考虑到可扩展性，节点类和链表类都是模板类（因此后缀需要是 `.hpp`），节点类定义如下

```c++
#define NULL 0

enum NodeType
{
	HEAD,
	TAIL,
	NORMAL
};

template<typename D>
class Node
{
public:
	Node(NodeType nodeType, D data) {
		setNodeType(nodeType);
		setData(data);
		prev = NULL;
		next = NULL;
	};
	Node(NodeType nodeType, D data, Node* prev, Node* next) {
		setNodeType(nodeType);
		setData(data);
		setPrev(prev);
		setNext(next);
	};
	~Node() {}

	D getData() { return data; }
	void setData(D data) { this->data = data; }
	Node* getPrev() { return prev; }
	void setPrev(Node* prev) { this->prev = prev; }
	Node* getNext() { return next; }
	void setNext(Node* next) { this->next = next; }
	NodeType getNodeType() { return nodeType; }
	void setNodeType(NodeType nodeType) { this->nodeType = nodeType; }
private:
	Node* prev;
	Node* next;
	D data;
	NodeType nodeType;
};
```

还有一些具体细节这里没有展示，详细见代码

链表类定义如下

```c++
template<typename T>
class LinkedList
{
public:
	LinkedList() {
		head = new Node<T>(HEAD, 0);
		tail = new Node<T>(TAIL, 0);
		head->setNext(tail);
		head->setPrev(tail);
		tail->setNext(head);
		tail->setPrev(head);
		size = 0;
		node = head;
	}
	~LinkedList() {};

	void addToTail(Node<T>* node);
	void addToTail(T data);
	void addToHead(Node<T>* node);
	void addToHead(T data);

	void remove(Node<T>* node);
	void remove(T data);

	Node<T>* selectFirstNode(T data);
	Node<T>* get(int index);

	Node<T>* getLastNode() { if (size > 0) return tail->getPrev(); else return head; }
	Node<T>* getFirstNode() { if (size > 0) return head->getNext(); else return head; }

	Node<T>* getHead() { return head; }
	Node<T>* getTail() { return tail; }
	int getSize() { return size; }
    
public:
	// 该部分迭代用

	bool hasNext() { return node->getNext()->getNodeType() == NORMAL; };
	bool hasPrev() { return node->getPrev()->getNodeType() == NORMAL; };
	Node<T>* next() {
		node = node->getNext();
		return node;
	}
	Node<T>* prev() {
		node = node->getPrev();
		return node;
	}
private:
	Node<T>* head;
	Node<T>* tail;
	int size;

	/* 当前节点指针 */
	Node<T>* node;
};
```

具体细节这里没有展示，详细见代码