抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

实现线性表List之链表

基础学习

发布于：2022年10月18日

次浏览

什么是链表

链表由若干节点构成,节点之间有链接,链接末尾没有节点,指向空null.

image-20221025134229495

链表的实现需要定义:

  • 泛型变量作为节点数据;
  • 下一个节点的引用;
  • 头节点。

代码实现单链表

using System;
using System.Text;

namespace AlgorithmTest08_链表
{
    /// <summary>
    /// 单链表
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class LinkedList1<T>
    {
        /// <summary>
        /// 节点类
        /// </summary>
        private class Node
        {
            public T t;//类型
            public Node next;//下一个
            public Node(T t, Node next)
            {
                this.t = t;
                this.next = next;
            }
            public Node(T t)
            {//链表尾
                this.t = t;
                this.next = null;
            }
            public override string ToString()
            {
                return t.ToString();
            }
        }

        /// <summary>
        /// 链表头
        /// </summary>
        private Node head;

        /// <summary>
        /// 链表中存储了多少元素
        /// </summary>
        private int N;

        /// <summary>
        /// 链表类构造函数初始化
        /// </summary>
        public LinkedList1()
        {
            head = null;
            N = 0;
        }
        /// <summary>
        /// 元素个数
        /// </summary>
        public int Count
        {
            get
            {
                return N;
            }
        }
        /// <summary>
        /// 是否为空
        /// </summary>
        public bool IsEmpty
        {
            get { return N == 0; }
        }
        /// <summary>
        /// 添加元素
        /// </summary>
        public void Add(int index, T t)
        {
            if (index < 0 || index > N)
            {
                throw new ArgumentException("非法索引");
            }
            if (index == 0)
            {
                //Node node = new Node(t);
                //node.next = head;
                //head = node;
                head = new Node(t, head);
            }
            else
            {
                Node pre = head;
                for (int i = 0; i < index - 1; i++)
                {
                    pre = pre.next;
                }
                //Node node = new Node(t);
                //node.next = pre.next;//新增节点的下一个节点,等于pre位置的下一个节点[相当于占了它位置]
                //pre.next = node;//pre的下一个节点为新增的节点,[相当于被挤到左侧]
                pre.next = new Node(t, pre.next);
            }
            N++;
        }
        /// <summary>
        /// 头部添加
        /// </summary>
        /// <param name="t"></param>
        public void AddFirst(T t)
        {
            Add(0, t);
        }

        /// <summary>
        /// 尾部添加
        /// </summary>
        /// <param name="t"></param>
        public void AddLast(T t)
        {
            Add(N, t);
        }
        /// <summary>
        /// 查询,index:索引
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T Get(int index)
        {
            if (index < 0 || index >= N)
            {
                throw new ArgumentException("非法索引");
            }
            Node cur = head;//当前位置
            for (int i = 0; i < index; i++)
            {
                cur = cur.next;
            }
            return cur.t;//返回,值
        }
        /// <summary>
        /// 获取头节点内容
        /// </summary>
        /// <returns></returns>
        public T GetFirst()
        {
            return Get(0);
        }
        /// <summary>
        /// 获取尾节点内容
        /// </summary>
        /// <returns></returns>
        public T GetLast()
        {
            return Get(N - 1);
        }
        /// <summary>
        /// 修改节点内容
        /// </summary>
        /// <param name="index"></param>
        /// <param name="newT"></param>
        public void Set(int index, T newT)
        {
            if (index < 0 || index >= N)
            {
                throw new ArgumentException("非法索引");
            }
            Node cur = head;//初始化当前节点
            for (int i = 0; i < index; i++)
            {
                cur = cur.next;
            }
            cur.t = newT;
        }
        /// <summary>
        /// 查找链表中是否有该元素
        /// </summary>
        /// <param name="t"></param>
        /// <returns></returns>
        public bool Contains(T t)
        {
            Node cur = head;
            while (cur != null)
            {
                if (cur.t.Equals(t))
                {
                    return true;
                }
                cur = cur.next;//右移
            }
            return false;
        }
        /// <summary>
        /// 删除索引处节点
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T RemoveAt(int index)
        {
            if (index < 0 || index >= N)
            {
                throw new ArgumentException("索引不合法");
            }
            if (index == 0)
            {//删除头部
                Node delNode = head;//接收原head数据
                head = head.next;
                N--;
                return delNode.t;
            }
            else
            {
                Node pre = head;
                for (int i = 0; i < index - 1; i++)
                {
                    pre = pre.next;
                }
                Node delNode = pre.next;
                pre.next = delNode.next;
                N--;
                return delNode.t;
            }
        }
        /// <summary>
        /// 删除头节点
        /// </summary>
        /// <returns></returns>
        public T RemoveFirst()
        {
            return RemoveAt(0);
        }
        /// <summary>
        /// 删除最后一个节点
        /// </summary>
        /// <returns></returns>
        public T RemoveLast()
        {
            return RemoveAt(N - 1);
        }

        public void Remove(T t)
        {
            if (head == null)
            {//如果链表为空则弹出
                return;
            }
            if (head.t.Equals(t))
            {//删除的值为头部,则直接调用
                RemoveFirst();
            }
            else
            {
                Node cur = head;
                Node pre = null;
                while (cur != null)
                {
                    if (cur.t.Equals(t))
                    {
                        break;
                    }
                    pre = cur;//第一轮pre移动到head,第二轮pre右移
                    cur = cur.next;//第一轮cur右移,第二轮cur右移
                    //直到查询到相同内容,弹出.或者cur为null(查到底了)
                }
                if (cur != null)
                {//删除操作,跳过cur
                    pre.next = pre.next.next;
                    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();
        }
    }
}

链表添加数据(带头节点)

若是在头节点添加,就是新节点的next指向头节点,然后新节点赋值给head，自己成为新的头节点。

若是正常添加新节点，就是index位-1进行循环遍历。移动定位节点到位置的前一个，然后定位节点的next指向新节点的next，新节点本身指向定位节点的next，成功插入。

代码实现:

/// <summary>
     /// 添加元素
     /// </summary>
     public void Add(int index, T t)
     {
         if (index < 0 || index > N)
         {
             throw new ArgumentException("非法索引");
         }
         if (index == 0)
         {
             //Node node = new Node(t);
             //node.next = head;
             //head = node;
             head = new Node(t, head);
         }
         else
         {
             Node pre = head;
             for (int i = 0; i < index - 1; i++)
             {
                 pre = pre.next;
             }
             //Node node = new Node(t);
             //node.next = pre.next;//新增节点的下一个节点,等于pre位置的下一个节点[相当于占了它位置]
             //pre.next = node;//pre的下一个节点为新增的节点,[相当于被挤到左侧]
             pre.next = new Node(t, pre.next);
         }
         N++;
     }
     /// <summary>
     /// 头部添加
     /// </summary>
     /// <param name="t"></param>
     public void AddFirst(T t)
     {
         Add(0, t);
     }
     /// <summary>
     /// 尾部添加
     /// </summary>
     /// <param name="t"></param>
     public void AddLast(T t)
     {
         Add(N, t);
     }

重写ToString

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();
}

测试:

class Program
{
    static void Main(string[] args)
    {
        LinkedList1<int> l = new LinkedList1<int>();
        Console.WriteLine("初次打印");
        for (int i = 0; i < 5; i++)
        {
            l.AddFirst(i);
            Console.WriteLine(l);
        }
        Console.WriteLine("末尾添加数字99:");
        l.AddLast(99);
        Console.WriteLine(l);
        Console.WriteLine("索引2添加222");
        l.Add(2, 2222222);
        Console.WriteLine(l);
        Console.WriteLine("查询索引2");
        Console.WriteLine(l.Get(2));
        Console.WriteLine("修改索引2");
        l.Set(2, 20);
        Console.WriteLine(l.Get(2));
        Console.WriteLine("查找链表中是否有值");
        Console.WriteLine(l.Contains(4));
        Console.ReadKey();
    }
}

image-20221025134259502

删除元素

头部:head.next指向下一个即可,其他部分:index前一个.next指向index.next

/// <summary>
/// 删除索引处节点
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T RemoveAt(int index)
{
    if (index < 0 || index >= N)
    {
        throw new ArgumentException("索引不合法");
    }
    if (index == 0)
    {//删除头部
        Node delNode = head;//接收原head数据
        head = head.next;
        N--;
        return delNode.t;
    }
    else
    {
        Node pre = head;
        for (int i = 0; i < index - 1; i++)
        {
            pre = pre.next;
        }
        Node delNode = pre.next;
        pre.next = delNode.next;
        N--;
        return delNode.t;
    }
}

测试结果:

image-20221025134328965

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://niaoyu00.github.io/Blog/2022/10/18/实现线性表List之链表/

更新于：2022年11月11日

数据结构与算法

评论