结构

image.png

单链表节点

  1.     //链表的节点
  2.     public class Node
  3.     {
  4.         #region 数据域
  5.         public int index;
  6.         public string str;
  7.         #endregion
  9.         #region 指针域
  10.         public Node next;//下一个节点
  11.         #endregion
  13.         //创建这个节点时，存入数据
  14.         public Node(int index,string str)
  15.         {
  16.             this.index = index;
  17.             this.str = str;
  18.         }
  19.     }

单链表对象类

  1.     public class SingleLinkList
  2.     {
  3.         public LinkNode head { get; } = new LinkNode(0, "");//头节点，这个节点没有具体数据，表示单链表的头（有些链表没有头节点）
  5.         //1.添加节点到链表末尾
  6.         //2.显示全部数据
  7.         //3.查询节点
  8.         //4.插入节点
  9.         //5.修改节点
  10.         //6.删除节点
  11.     }

1.添加节点到末尾

在SingleLinkList类里面的方法
image.png

  1.         //添加节点到链表的末尾
  2.         public void AddLast(LinkNode node)
  3.         {
  4.             //找到当前链表的最后一个节点，将最后一个节点的next指向这个新的节点
  5.             LinkNode temp = head;//声明一个临时指针，先指向链表头
  6.             while (true)//循环遍历这个链表的节点
  7.             {
  8.                 if (temp.next == null)
  9.                 {
  10.                     //如果当前节点的下一个节点为null，就说明当前节点就是最后一个了，因此退出循环
  11.                     break;
  12.                 }
  13.                 //如果没有退出当前循环，就说明没有到最后一个节点，这个临时指针就指向下一个节点
  14.                 temp = temp.next;
  15.             }
  16.             //退出循环就说明找到了最后一个节点，temp就是最后一个节点，连接上新的节点，添加完成
  17.             temp.next = node;
  18.         }

2.显示全部节点

在SingleLinkList类里面的方法
就是遍历一遍链表。

  1.         //显示链表全部数据
  2.         public void Show()
  3.         {
  4.             if (head.next == null)
  5.             {
  6.                 Console.WriteLine("链表为空");
  7.                 return;
  8.             }
  9.             LinkNode temp = head.next;//链表不为空的话至少有一个数据
  10.             while (true)
  11.             {
  12.                 Console.WriteLine(temp.index + temp.str);
  13.                 if (temp.next == null)
  14.                 {
  15.                     break;
  16.                 }
  17.                 temp = temp.next;
  18.             }
  19.         }

3.查询节点

在SingleLinkList类里面的方法

  1.         //根据str查找数据节点
  2.         public LinkNode Select(string str)
  3.         {
  4.             if (head.next == null)
  5.             {
  6.                 Console.WriteLine("链表为空");
  7.                 return null;
  8.             }
  9.             LinkNode temp = head.next;
  10.             bool isFind = false;//一个标记,表示有没有查询到数据
  11.             while (true)
  12.             {
  13.                 if (temp.str == str)//查到了数据，退出循环，temp就是要找的节点
  14.                 {
  15.                     isFind = true;
  16.                     break;
  17.                 }
  18.                 if (temp.next == null)//最后一个节点了
  19.                 {
  20.                     break;
  21.                 }
  23.                 temp = temp.next;
  24.             }
  25.             if (isFind)//找到了数据就返回temp这个数据节点
  26.             {
  27.                 return temp;
  28.             }
  29.             else//没找到就返回空
  30.             {
  31.                 return null;
  32.             }
  33.         }

4.插入节点

在SingleLinkList类里面的方法
image.png

  1.         //添加的时候按顺序某个值的顺序添加，也叫插入
  2.         public void AddOrder(LinkNode node)
  3.         {
  4.             LinkNode temp = head;
  5.             bool isExist = false;//添加的节点的某个值是否 已经存在
  6.             while (true)
  7.             {
  8.                 if (temp.next==null)//先判断是不是在最后，当前节点在链表最后就退出循环
  9.                 {
  10.                     break;
  11.                 }
  12.                 //当前节点的下一个节点比新节点的数据大，那么新节点插入到当前节点和下一个节点之间。（我这里是升序，降序思路反过来）
  13.                 if (temp.next.index > node.index)
  14.                 {
  15.                     break;
  16.                 }
  17.                 if (temp.index == node.index)//如果发现值一样的就不能添加了，当然这个判断重复根据情况而定，有些需要有些不需要
  18.                 {
  19.                     isExist = true;
  20.                     break;
  21.                 }
  22.                 temp = temp.next;
  23.             }
  25.             if (isExist)
  26.             {
  27.                 Console.WriteLine("已经存在了不能添加");
  28.                 return;
  29.             }
  30.             else
  31.             {
  32.                 //用新节点next指向下一个节点，当前节点next指向新节点，新节点就插入到中间了，链子又连接起来了
  33.                 node.next = temp.next;
  34.                 temp.next = node;
  35.             }
  37.         }

5.修改节点

在SingleLinkList类里面的方法

  1.         //通过index值修改节点数据
  2.         public void Update(LinkNode node)
  3.         {
  4.             if (head.next == null)
  5.             {
  6.                 Console.WriteLine("链表为空");
  7.                 return;
  8.             }
  9.             LinkNode temp = head.next;
  10.             bool isFind = false;//是否找到对应要修改的节点
  11.             while (true)
  12.             {
  13.                 if (temp.index == node.index)//找到了节点
  14.                 {
  15.                     isFind = true;
  16.                     break;
  17.                 }
  18.                 if (temp.next == null)//最后一个节点了
  19.                 {
  20.                     break;
  21.                 }
  22.                 temp = temp.next;
  23.             }
  24.             if (isFind)
  25.             {
  26.                 //找到了就修改节点数据
  27.                 temp.str = node.str;
  28.             }
  29.             else
  30.             {
  31.                 Console.WriteLine("没有找到该节点");
  32.             }
  33.         }

6.删除节点

在SingleLinkList类里面的方法
image.png

  1.         //通过index删除对应的节点
  2.         public void Delete(int index)
  3.         {
  4.             if (head.next == null)
  5.             {
  6.                 Console.WriteLine("链表为空");
  7.             }
  8.             LinkNode temp = head;
  9.             bool isFind = false;//是否找到对应的节点
  10.             while (true)
  11.             {
  12.                 if (temp.next == null)
  13.                 {
  14.                     break;
  15.                 }
  16.                 //temp表示要删除节点的上一个节点，如果temp直接代表这个要删除的节点，那要删除的节点的上一个和下一个节点无法连接
  17.                 if (temp.next.index==index)
  18.                 {
  19.                     isFind = true;
  20.                     break;
  21.                 }
  22.                 temp = temp.next;
  23.             }
  24.             if (isFind)
  25.             {
  26.                 //要删除的节点是temp.next，把temp指向temp.next.next，中间temp.next没有引用就删除了
  27.                 temp.next = temp.next.next;
  28.             }
  29.             else
  30.             {
  31.                 Console.WriteLine("没有找到数据");
  32.             }
  33.         }

单链表题

1.得到单链表有效节点个数

就是遍历，计数

  2. //单链表有效节点的个数，传入上方单链表的头节点，头结点不算有效节点
  3. static int SingleLinkListCount(LinkNode head)
  4. {
  5.     //有头节点的要去掉头节点
  6.     if (head.next == null)
  7.     {
  8.         return 0;
  9.     }
  10.     LinkNode temp = head.next;
  11.     int count = 0;
  12.     while (temp != null)
  13.     {
  14.         count++;
  15.         temp = temp.next;
  16.     }
  17.     return count;
  18. }

2.查找单链表中倒数第k个节点

思路：

  1. 从链表头到尾遍历得到有效节点个数
  2. 得到链表的有效节点个数size后，从头开始遍历到（size-k）个就可以得到

  3. 找到返回该节点，否这返回null

    1.      /*查找单链表中倒数第k个元素*/
    2.      static LinkNode FindLast_k_Node(LinkNode head,int k)
    3.      {
    4.          if (head.next == null)//链表为空
    5.          {
    6.              return null;
    7.          }
    8.          LinkNode temp = head.next;
    9.          int size = SingleLinkListCount(head);//调用上面的方法得到链表有效数据个数
    10.          //用for限制遍历到size-k为止
    11.          for(int i = 0; i < size - k; i++)
    12.          {
    13.              //不用做什么，就迭代到下一个，最后一个就是倒数第k个元素
    14.              temp = temp.next;
    15.          }
    16.          return temp;
    17.      }

    3.单链表的反转

    思路：

  4. 先定义一个节点LinkNode reverseHead = new LinkNode();

  5. 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
  6. 原来链表的head.next=reverseHead.next

图解

image.png
image.png

image.png
image.png

  1.         static void reverseLinkList(LinkNode head)
  2.         {
  3.             //链表为空或者只有一个节点，不用反转
  4.             if (head.next == null || head.next.next == null)
  5.             {
  6.                 return;
  7.             }
  9.             //定义一个辅助指针，帮助遍历原来的链表
  10.             LinkNode cur = head.next;
  11.             LinkNode next = null;//指向当前节点（cur）的下一个节点
  12.             LinkNode reverseHead = new LinkNode(0,"");//反转的开始节点
  13.             while (cur != null)
  14.             {
  15.                 next = cur.next;//把当前节点的下一个节点暂时保存在next里面，因为要把reverseHead.next放在当前节点的next
  16.                 cur.next = reverseHead.next;//想象cur是反转链表的第一个，就要把反转链表之后的节点都放在cur之后
  17.                 reverseHead.next = cur;//cur放在reverseHead反转链表头的第一个
  18.                 cur = next;//当前节点后移
  19.             }
  20.             head.next = reverseHead.next;//原链表的head指向反转链表的next
  21.         }

4.从尾到头打印单链表

思路：
方式1先反转单链表，再遍历打印。这样做会破坏原来的单链表的结构。
方式2利用栈这个数据结构，将各个节点压入栈中，利用栈的先进后出的特点，就实现了逆序打印的效果

这里使用方式2
先写一个简单的栈结构

  1.     public class SimpleStack<T>
  2.     {
  3.         T[] t = null;
  4.         int top = -1;//栈顶部默认-1，初始没有数据
  5.         public SimpleStack(int i)
  6.         {
  7.             t = new T[i];
  8.         }
  10.         //入栈
  11.         public void Push(T t)
  12.         {
  13.             if (top + 1 >= this.t.Length)
  14.             {
  15.                 Console.WriteLine("栈满了");
  16.                 return;
  17.             }
  18.             else
  19.             {
  20.                 top++;
  21.                 this.t[top] = t;
  22.             }
  23.         }
  24.         //出栈
  25.         public T Pop()
  26.         {
  27.             if (top == -1)
  28.             {
  29.                 Console.WriteLine("栈没有数据");
  30.                 return default(T);
  31.             }
  32.             return this.t[top--];
  33.         }
  35.     }

然后，遍历链表入栈，遍历出栈

  1.         //反转打印链表,传入第一个有效节点
  2.         static void showReverseLinkList(LinkNode node)
  3.         {
  4.             SimpleStack<LinkNode> stack = new SimpleStack<LinkNode>(10);
  5.             while (node != null)
  6.             {
  7.                 stack.Push(node);
  8.                 node = node.next;
  9.             }
  10.             while (true)
  11.             {
  12.                 LinkNode linknode = stack.Pop();
  13.                 if (linknode == null)
  14.                     break;
  15.                 Console.WriteLine(linknode.index+linknode.str);
  16.             }
  17.         }