c++的链表-链表入门（C++）

囍楽云

发布于 2022-12-26 14:47:04

7840

发布于 2022-12-26 14:47:04

文章被收录于专栏：囍楽云博客

从上的链表基础知识学习，进行总结如下：

1.单链表介绍

单链表与数组不同，数组中只存储元素的值，而单链表中除了数据的值外还包括了指向下一个节点的引用字段通常以next来表示。如下图表示，通过这个引用，单链表将所有节点按照顺序组织起来。

通常单链表如下定义：

// Definition for singly-linked list.

    struct SinglyListNode {
        int val;
        SinglyListNode *next;
        SinglyListNode(int x) : val(x), next(NULL) {}

与数组区别，我们无法随机访问链表中的元素，但如果我们想要获得第i个元素就需要从头指针开始遍历。平均时间复杂度为O(N)。

2.链表添加

链表添加又分为在中间添加、在头部添加以及在尾部添加，首先是头部添加：

头结点是整个链表的代表因此在头部进行添加节点时最重要的是添加后更新head：

初始化一个cur；将该结点连接到head上；将cur指定为head.

中间位置添加：

首先初始化cur

将cur->next连接到pred的下一个节点即pred->next

最后将断掉的pred->next 再连接到cur上。

这样与数组进行对比我们只需要O(1)的时间复杂度就可以将元素插入进链表。

3.删除操作

如果我们想要删除一个节点cur，那我们需要两步：

找到cur的上一个节点以及下一个节点；

连接上一个节点pred到cur下一个节点.

因为cur节点的下一个节点就是cur->nextc++的链表，但是上一个节点需要遍历才可以找到c++的链表，因此删除节点的时间复杂度为O(N)。

如果要删除第一个节点我们只需要把下一个节点赋予head即可。

4.设计链表

class MyLinkedList {

    public:
        struct node{
            int val;
            node *next;
            node(int x): val(x),next(NULL){};
        };
        
        /** Initialize your data structure here. */
        MyLinkedList() {
            head = new node(0);
            size = 0;
        }
        
        /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
        int get(int index) {
            if(index(size-1)) return -1;
            node *cur = head->next;    //辅助指针指向第一个节点
            while(index--) cur = cur->next;
            return cur->val;
        }
        
        /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
        void addAtHead(int val) {
            node *cur = new node(val);
            cur->next = head->next;
            head->next = cur;
            size++;
        }
        
        /** Append a node of value val to the last element of the linked list. */
        void addAtTail(int val) {
            node *cur = head;
            while(cur->next)
            {
                cur = cur->next;
            }
            node *newnode = new node(val);
            newnode->next = cur->next;    //把结尾最后一个节点信息保存下来
            cur->next = newnode;          //将新节点连接在cur之后
            size++;
        }
        
        /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
        void addAtIndex(int index, int val) {
            if(index==0) addAtHead(val);
            else if(index == size) addAtTail(val);
            else if(index > size) return;
            else{
                node *pred = head;     //是在indexth之前插入 之后可以head->next
                node *ans = new node(val);
                //node *cur = new node(0);
                while(index>0)
                {
                    pred = pred->next;
                    index--;
                }
                ans->next = pred->next;
                pred->next = ans;
                size++;
            }
        }
        
        /** Delete the index-th node in the linked list, if the index is valid. */
        void deleteAtIndex(int index) {
            if(index < 0 || index >=size)
            return;
            node *cur = head;
            while(index>0)
            {
                cur = cur->next;
                index--;
            }
            cur->next = cur->next->next;
            size--;
        }
    private:
        int size;
        node *head;
    };
    /**
     * Your MyLinkedList object will be instantiated and called as such:
     * MyLinkedList* obj = new MyLinkedList();
     * int param_1 = obj->get(index);
     * obj->addAtHead(val);
     * obj->addAtTail(val);
     * obj->addAtIndex(index,val);
     * obj->deleteAtIndex(index);