【数据结构】单链表

单链表

一、单链表定义

含有一个数据域和一个指针域，由指针域连接下一个结点，依次将整个链表的所有结点串起来的数据结构。

二、带头/不带头

头结点是有效数据就是不带头的链表，反之，头结点不存储有效数据就是带头的链表。

三、结点定义

// 节点结构体
    class ListNode {
    public:
        T val;
        ListNode* next;

        ListNode() {}

        explicit ListNode(T val) {
            this->val = val;
            next = nullptr;
        }
    };
1
2
3
4
5
6
7
8
9
10
11
12
13

使用 explicit 避免单参数构造函数进行隐式转换。

四、尾插

创建一个cur 指针，从头结点开始指，遍历到链表末尾，然后进行尾插。

与顺序表不同的是，尾插的时候不需要进行判满，链表随插，随new结点。

// 尾插
template<class T>
void SingleList<T>::push_back(T val)
{
	// 创建新节点
	ListNode* newNode = new ListNode(val);

	// 遍历到最后
	ListNode* cur = first;
	while (cur->next != NULL) {
		cur = cur->next;
	}

	cur->next = newNode;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

五、清空

清空操作不能直接delete first 因为在first后面还跟着许多的结点，他们都是new出来的，这样会导致其他的结点并未释放， 形成假清空。

代码：

void clear()
	{
		while (first != nullptr) {
			ListNode<T>* next = first->next;
			delete first;
			first = nullptr;
			first = next;
		}
	}
1
2
3
4
5
6
7
8
9

六、 删除

找到deleteNode 的前一个结点，将prevNode 的nex串到nextNode。

然后再进行释放deleteNode。