数据结构——链表（C++代码实现）

向右看齐 2022-12-20 01:59 126阅读 0赞

# 链表的介绍 #

链表是由元素之间互相依赖，串联而成的。链表存储的每一个元素，都是由数据域和指针域两部分组成，称为链表的一个结点。数据域存储数据，指针域存储下一结点的地址。

# 链表的特点 #

链表的内存空间是不连续的，这导致链表无法做随机访问的操作，获取数据只能从头往后遍历；数组与链表相比，不是查询快，而是数组可以随机访问，很多人会把查询和随机访问混淆了，查询是查找存储的特定数据，随机访问是访问指定位置的内容。

# 链表的实现 #

下面来用C++代码实现链表的构建、插入、遍历、删除功能。

## 1.单链表 ##

#include <iostream>
    using std::cin;
    using std::cout;
    using std::endl;
    
    template <typename Type> class Node {
        //首先定义链表的结点类
    public:
        Type data;//存储数据的变量
        Node<Type> *next;//存储下一结点的地址的指针
        Node(const Type &_data) {
        
            data = _data;
            next = NULL;
        }
    };
    template <typename Type> class LinkedList {
        //定义链表类
    private:
        Node<Type> *head;//存储链表头结点地址的指针
    public:
        LinkedList() {
        //构建一个新链表对象
            head = NULL;//新链表没有结点，head指向空地址
        }
        ~LinkedList() {
        
            Node<Type> *current_node = head;
            while (current_node != NULL) {
        
                Node<Type> *delete_node = current_node;
                current_node = current_node->next;
                delete delete_node;
            }
        }
        void insert(Node<Type> *node, int index) {
        
            if (head == NULL) {
        //插入元素前判断链表是否为空
                if (index != 0) {
        //链表为空，且插入位置不是头结点位置时，不执行插入操作
                    return ;
                }
                head = node;//链表为空，且插入位置为头结点位置时，head指向新结点
                return ;
            }
            if (index == 0) {
        //链表不为空，且插入位置为头结点位置时
                node->next = head;//新结点指向目前的头结点
                head = node;//更新头结点，head指针指向新结点
                return ;
            }
            //一般的插入操作
            Node<Type> *current_node = head;//定义当前结点指针
            int count = 0;//记录经过的结点数
            while ((current_node->next != NULL) && (count < index - 1)) {
        //循环找到插入位置的前一个结点
                current_node = current_node->next;
                count++;
            }
            if (count == index - 1) {
        //判断插入的位置是否超出链表长度，没有超出才执行插入操作
                node->next = current_node->next;//新结点指向当前结点的下一个结点
                current_node->next = node;//当前结点指向新结点
                return ;
            }
            return ;
        }
        void output() {
        
            if (head == NULL) {
        //链表为空，不执行遍历操作
                return;
            }
            Node<Type> *current_node = head;//定义当前结点指针
            while (current_node->next != NULL) {
        //当前结点没有指向空地址，则不断向后遍历
                cout << current_node->data << " ";
                current_node = current_node->next;
            }
            cout << current_node->data << endl;
        }
        void delete_node(int index) {
        
            if (head == NULL) {
        //链表为空，不执行删除操作
                return ;
            }
            Node<Type> *current_node = head;//定义当前结点指针
            if (index == 0) {
        //当删除头结点时
                head = head->next;//head指向头结点的下一个结点，完成更新头结点
                delete current_node;//删除旧头结点的地址空间
                return;
            }
            //一般的删除操作
            int count = 0;//记录经过的结点数
            while ((current_node->next != NULL) && (count < index - 1)) {
        //循环找到删除位置的前一个结点
                current_node = current_node->next;
                count++;
            }
            if ((count == index - 1) && (current_node->next != NULL)) {
        //删除的位置不超过链表长度
                Node<Type> *delete_node = current_node->next;//定义指针指向删除的结点
                current_node->next = delete_node->next;//当前结点指向删除结点的下一个结点
                delete delete_node;//删除结点的地址空间
                return;
            }
            return;
        }
    };

## 2.循环链表 ##

循环链表需要注意的是，head指针指向的不再是头结点，而是指向尾结点；尾结点不指向空地址，而是指向头结点。

#include<iostream>
    using std::cin;
    using std::cout;
    using std::endl;
    template <typename Type> class Node {
        
    public:
        Type data;
        Node<Type> *next;
        Node(const Type &_data) {
        
            data = _data;
            next = NULL;
        }
    };
    template <typename Type> class CircularLinkedList {
        
    private:
        Node<Type> *head;
    public:
        LinkedList() {
        
            head = NULL;
        }
        ~LinkedList() {
        
            if (head == NULL) {
        
                return;
            }
            Node<Type> *current_node = head->next;//定义指针指向第一个结点
            head->next = NULL;//尾结点指向空，打断循环
            while (current_node != NULL) {
        
                Node<Type> *delete_node = current_node;
                current_node = current_node->next;
                delete delete_node;
            }
        }
        void insert(Node<Type> *node, int index) {
        
            if (head == NULL) {
        
                if (index != 0) {
        
                    return;
                }
                head = node;
                head->next = head;
                return;
            }
            if (index == 0) {
        
                node->next = head->next;//head->next才是头结点
                head->next = node;
                return;
            }
            Node<Type> *current_node = head->next;
            int count = 0;
            while ((current_node != head) && (count < index - 1)) {
        //判断条件改变
                current_node = current_node->next;
                count++;
            }
            if (count == index - 1) {
        
                node->next = current_node->next;
                current_node->next = node;
                if (node == head->next) {
        //增加判断是否插入到尾结点之后了，是则更新尾结点
    	            head = node;
    	        }
            }
        }
        void output() {
        
            if (head == NULL) {
        
                return;
            }
            Node<Type> *current_node = head->next;
            while (current_node != head) {
        //尾结点代替NULL地址
                cout << current_node->data << " ";
                current_node = current_node->next;
            }
            cout << current_node->data << endl;
        }
        void delete_node(int index) {
        
        	if (head == NULL) {
        
        		return;
        	}
            Node<Type> *current_node = head->next;
            if (index == 0) {
        
                head->next = current_node->next;
                delete current_node;
                return;
            }
    
            int count = 0;
            while ((current_node != head) && (count < index - 1)) {
        //判断条件与插入操作一致
                current_node = current_node->next;
                count++;
            }
            if ((count == index - 1) && (current_node != head)) {
        //判断条件改变
                Node<Type> *delete_node = current_node->next;
                current_node->next = delete_node->next;
                if (delete_node == head) {
        //判断是否删除尾结点了，是则更新尾结点
                	head = current_node;
                }
                delete delete_node;
                return;
            }
            return;
        }
    };

## 3.双向循环链表 ##

双向循环链表比单向循环链表存储的元素的指针域多了一个向前指的指针。

#include<iostream>
    using std::cin;
    using std::cout;
    using std::endl;
    template <typename Type> class Node {
        
    public:
        Type data;
        Node<Type> *next;
        Node<Type> *prior;//结点的指针域增加向前的指针
        Node(const Type &_data) {
        
            data = _data;
            next = NULL;
            prior = NULL;
        }
    };
    template <typename Type> class DoubleLinkedList {
        
    private:
        Node<Type> *head;
    public:
        LinkedList() {
        
            head = NULL;
        }
        ~LinkedList() {
        
            if (head == NULL) {
        
                return;
            }
            Node<Type> *current_node = head->next;
            head->next = NULL;
            while (current_node != NULL) {
        
                Node<Type> *delete_node = current_node;
                current_node = current_node->next;
                delete delete_node;
            }
        }
        void insert(Node<Type> *node, int index) {
        
            if (head == NULL) {
        
                if (index != 0) {
        
                    return;
                }
                head = node;
                head->next = head;
                head->prior = head;//增加前指向
                return;
            }
            if (index == 0) {
        
                node->next = head->next;
                node->prior = head;//新结点前指向尾结点
                head->next->prior = node;//头结点前指向新结点
                head->next = node;
                return;
            }
            Node<Type> *current_node = head->next;
            int count = 0;
            while ((current_node != head) && (count < index - 1)) {
        
                current_node = current_node->next;
                count++;
            }
            if (count == index - 1) {
        
                node->next = current_node->next;
                node->prior = current_node;//新结点前指向当前结点
                current_node->next->prior = node;//当前结点的下一结点前指向新结点
                current_node->next = node;
                if (node == head->next) {
        
                	head = node;
                }
                return;
            }
            return;
        }
        void output(int method = 0) {
        
            Node<Type> *current_node = head->next;
            if (method == 0) {
        //默认从前向后遍历
    	        while(current_node != head) {
        
    	        	cout << current_node->data << " ";
    	        	current_node = current_node->next;
    	        }
    	        cout << current_node->data << endl;
    	        return;
    	    } else {
        //选择从后向前遍历
    	    	while(current_node != head) {
        
    	        	cout << current_node->data << " ";
    	        	current_node = current_node->prior;
    	        }
    	        cout << current_node->data << endl;
    	        return;
    	    }
        }
        void delete_node(int index) {
        
        	if (head == NULL) {
        
        		return;
        	}
            Node<Type> *current_node = head->next;
            if (index == 0) {
        
                head->next = current_node->next;
                current_node->next->prior = head;//头结点的下一结点前指向尾结点
                delete current_node;
                return;
            }
            int count = 0;
            while ((current_node != head) && (count < index - 1)) {
        
                current_node = current_node->next;
                count++;
            }
            if ((count == index - 1) && (current_node != head)) {
        
                Node<Type> *delete_node = current_node->next;
                current_node->next = delete_node->next;
                delete_node->next->prior = current_node;//删除结点的下一结点前指向当前结点
                if (delete_node == head) {
        
                	head = current_node;
                }
                delete delete_node;
                return;
            }
            return;
        }
    };