线性表中的单链表

顺序表与单链表的区别

顺序表中的数据在内存中是顺序存放的，在创建顺序表的时候就需要在内存中开辟连续的存储空间，如果需要开辟很大的空间有可能会找不到足够大的连续空间而创建失败。顺序表的查找为随机查找，时间复杂度为O(1)级别。

线性表中的每个节点随机的分布在内存中，不需要连续分布，更好的利用了内存空间，但是线性表的查找时间复杂度为O(n)。

关键代码

类定义

template <class T>
 class LNode //单链表节点
 {
 public:
     T data;                                   //数据域
     struct LNode *next;                       //指针域
     LNode(T data) : data(data), next(NULL) {} //有参构造
     LNode() : next(NULL) {}                   //无参构造
 };

带头结点的头插法创建链表,n为数据数量

template <class T>
 LinkList<T> List_HeadInsert(LinkList<T> &head, int n) //带头结点的头插法创建链表,n为数据数量
 {
     head = new LNode<T>; //头节点
     head->next = NULL;   //后继节点置空
     T data;              //数据
     for (int i = 0; i < n; i++)
    {
         cin >> data;                      //读取输入
         LNode<T> *s = new LNode<T>(data); //创建新的节点
         s->next = head->next;             //插入到头部
         head->next = s;                   //数据
    }
     return head; //返回头节点
 }

插入节点中的前插

template <class T>
 LinkList<T> FrontInsert(LinkList<T> head, T data, int i) //前插法，将值为data的新节点插入到链表第i个位置前面
 {
     if (i < 1 || i > GetLength(head)) //非法输入
         return NULL;
     LNode<T> *r = GetElem(head, i);            //调用查找第i个节点函数
     LNode<T> *newNode = new LNode<T>(r->data); //新节点
     r->data = data;
     newNode->next = r->next; //插入,本质为后插+交换第i个节点与新节点的值
     r->next = newNode;
     return head;
 }

删除节点

template <class T>
 LinkList<T> Delete(LinkList<T> head, int i) //删除第i个节点
 {
     if (i < 1 || i > GetLength(head)) //非法输入
         return NULL;
     LNode<T> *p = GetElem(head, i - 1); //定位为到第i-1个节点的位置
     LNode<T> *q = p->next;
     p->next = q->next; //删除
     delete q;
 }

 

项目地址

https://gitee.com/incoparab/data-structure

标签：学习笔记, c/c++