定义

链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。
链表和数组比较，不用事先确定存储空间，而是根据需要开辟内存单元。

表现示例

第0个结点称为头结点，它存放有第一个结点的首地址，它没有数据，只是一个指针变量。
以下的每个结点都分为两个域。

一个是数据域，存放各种实际的数据，如学号num，姓名name，性别sex和成绩score等。
一个域为指针域，存放下一结点的首地址。链表中的每一个结点都是同一种结构类型
优势
链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。

链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。

名称注释

首节点

存放第一个有效数据的节点头节点：在单链表的第一个结点之前附设一个结点，它没有直接前驱，称之为头结点，头结点的数据域可以不存储任何信息，指针域指向第一个节点(首节点)的地址。头结点的作用是使所有链表(包括空表)的头指针非空

头指针

指向头节点的指针

尾节点

存放最后一个有效数据的节点

尾指针

指向尾节点的指针

链表就如同车链子一样， head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”(表示“空地址”) ，链表到此结束。

作为有强大功能的链表，对他的操作当然有许多，比如：链表的创建，修改，删除，插入，输出，排序，反序，清空链表的元素，求链表的长度等等。

操作

链表中添加结点

链表头部插入结点(头插法)

假设有以下链表

建立一个新结点，它的下一结点指向null
Node node = new Node(5);
QQ截图20220419094434.png
把新结点的下一结点指向head结点
node.next = head;

更新头结点，head指向新结点
head = node;
完成往链表头部插入结点

往链表中间或尾部插入结点

假设往结点1后插入新结点6，找到结点1的下一结点指向6，6的下一结点指向结点2即可

Node pre = head;
for(int i = 0; i < index - 1; i++)
{
    pre = pre.next;
}

Node node = new Node(6);
node.next = pre.next;

pre的下一结点指向6
pre.next = node;

查询链表中的结点

利用临时变量cur
Node cur = head;

for(int i = 0; i < index; i++)
 cur = cur.next;

删除链表中的结点

删除链表头部结点

删除结点5，只需把头结点指向结点5的下一结点
head = head.next;

结点5没有引用会被回收。

删除链表中间或尾部的结点

假设要删除索引位置3的结点

Node pre=head;
for(int i = 0; i < index - 1; i++)
{
     pre = pre.next;
}

Node delNode = pre.next;
pre.next = delNode.next;

删除链表中指定的结点

假如删除结点6

临时变量cur结点指向head，临时pre结点指向null

pre = cur;
cur = cur.next;

具体代码实现

using System;
using System.Collections.Generic;
using System.Text;
namespace LinkedList
{
    class LinkedList1<E> // 泛型链表类
    {
        // 结点内部类
        private class Node
        {
            public E e;         // 存储的元素e
            public Node next;   // 当前结点的下一个结点
            // 构造函数初始化
            public Node(E e, Node next)
            {
                this.e = e;
                this.next = next;
            }
            // 没有下一结点的构造
            public Node(E e)
            {
                this.e = e;
                this.next = null;
            }
            // 打印输出
            public override string ToString()
            {
                return e.ToString();
            }
        }
        // 链表头部
        private Node head;
        // 存储的元素个数
        private int N;
        // 构造函数
        public LinkedList1()
        {
            head = null;
            N = 0;
        }
        // 属性：链表元素个数
        public int Count
        {
            get { return N; }
        }
        // 属性：是否为空
        public bool IsEmpty
        {
            get { return N == 0; }
        }
        // 插入结点
        public void Add(int index, E e)
        {
            if (index < 0 || index > N)
            {
                throw new ArgumentException("非法索引");
            }
            // 往头部插入结点
            if (index == 0)
            {
                Node node = new Node(e);    // 创建新结点
                node.next = head;           // 新结点next指向头结点
                head = node;                // 更新头结点
                //head = new Node(e, head);     这里复用了之前写的public Node(E e,Node next)构造方法，等同于上面三行代码一样
            }
            // 往中间或尾部插入
            else
            {
                Node pre = head;                    // 临时结点pre
                for (int i = 0; i < index - 1; i++) // 找到要插入的索引位置的结点的前一个结点
                {
                    pre = pre.next;
                }
                Node node = new Node(e);    // 创建新结点
                node.next = pre.next;       // 新结点指向临时结点下一结点
                pre.next = node;            // 更新临时结点下一结点指向新结点
                //pre.next = new Node(e, pre.next); 同理等同于上面三句代码
            }
            N++;// 链表元素个数更新
        }
        // 头部插入
        public void AddFirst(E e)
        {
            Add(0, e);
        }
        // 尾部插入
        public void AddLast(E e)
        {
            Add(N, e);
        }
        // 查询结点
        public E Get(int index)
        {
            if (index < 0 || index >= N)
            {
                throw new ArgumentException("非法索引");
            }                
            Node cur = head;    // 临时变量结点cur指向结点head
            // 找到对应索引结点
            for (int i = 0; i < index; i++)
            {
                cur = cur.next;
            }
            return cur.e;
        }
        public E GetFirst()
        {
            return Get(0);
        }
        public E GetLast()
        {
            return Get(N - 1);
        }
        // 修改结点元素
        public void Set(int index, E newE)
        {
            if (index < 0 || index >= N)
                throw new ArgumentException("非法索引");
            Node cur = head;                    // 临时变量结点cur指向结点head
             // 找到对应索引结点
            for (int i = 0; i < index; i++)    
            {
                cur = cur.next;
            }
            cur.e = newE;
        }
        // 判断包含
        public bool Contains(E e)
        {
            Node cur = head;
            while (cur != null)
            {
                // 如果结点与元素相同返回true
                if (cur.e.Equals(e))
                {
                    return true;
                }                    
                cur = cur.next;
            }
            return false;
        }
        public E RemoveAt(int index)//删除
        {
            if (index < 0 || index >= N)
                throw new ArgumentException("非法索引");
            //删除头结点
            if (index == 0)
            {
                Node delNode = head;    // delNode指向head结点
                head = head.next;       // 更新头结点
                N--;
                return delNode.e;       // 返回被删除的结点元素
            }
            else
            {
                Node pre = head;
                // 找到删除索引结点的前一个结点
                for (int i = 0; i < index - 1; i++)     
                    pre = pre.next;
                Node delNode = pre.next;                // delNode指向pre结点的下一个结点
                pre.next = delNode.next;                // pre下一个结点指向delNode的下一个结点
                N--;
                return delNode.e;
            }
        }
        public E RemoveFirst()
        {
            return RemoveAt(0);
        }
        public E RemoveLast()
        {
            return RemoveAt(N - 1);
        }
        public void Remove(E e)
        {
            // 头结点空，说明链表没有结点
            if (head == null)
            {
                return;
            }
            // 删除的元素是头结点
            if (head.e.Equals(e))
            {
                head = head.next;
                N--;
            }
            else
            {
                Node cur = head;
                Node pre = null;
                // 查找要删除的元素的结点
                while (cur != null) 
                {
                    // 找到元素退出循环
                    if (cur.e.Equals(e))
                    {
                        pre.next = cur.next; // pre下一结点指向cur的下一结点
                        break;
                    }
                    pre = cur;
                    cur = cur.next;
                }
                //if (cur != null)
                //{
                //    pre.next = pre.next.next; // pre下一结点指向cur的下一结点
                //    N--;
                //}
            }
        }
        // 打印输出
        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            Node cur = head;
            while (cur != null)
            {
                res.Append(cur + "->");
                cur = cur.next;
            }
            res.Append("Null");
            return res.ToString();
        }
    }
}

using System;
namespace LinkedList
{
    class Program
    {
        static void Main(string[] args)
        {
            // 创建链表
            LinkedList1<int> l = new LinkedList1<int>();
            for (int i = 0; i < 5; i++)
            {
                l.AddFirst(i);            // 头部插入
                Console.WriteLine(l);
            }
            l.AddLast(60);                //  尾部插入
            Console.WriteLine("尾部插入");
            Console.WriteLine(l);
            l.Add(2, 99);
            Console.WriteLine("索引2位置插入99结点");
            Console.WriteLine(l);
            l.Set(1, 100);
            Console.WriteLine("修改索引1位置的结点元素");
            Console.WriteLine(l);
            l.RemoveAt(2);
            Console.WriteLine("删除索引2位置的结点");
            Console.WriteLine(l);
            l.RemoveFirst();
            Console.WriteLine("删除头结点");
            Console.WriteLine(l);
            l.RemoveLast();
            Console.WriteLine("删除尾部结点");
            Console.WriteLine(l);
            l.Remove(0);
            Console.WriteLine("删除结点0");
            Console.WriteLine(l);
            Console.Read();
        }
    }
}

链表

定义