C#数据结构-单链表双链表环形链表

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

链表特点(单链表双链表)

优点：插入和删除非常快。因为单链表只需要修改Next指向的节点，双链表只需要指向Next和Prev的节点就可以完成插入和删除操作。

缺点：当需要查找某一个节点的时候就需要一个节点一个节点去访问，这样所花的时候就比较多了。(顺序表可以弥补这缺点，但插入和删除就非常耗性能)

单链表

单链表的构成：必须要有一个链表头（head）,每个节点里面有一个Next用于指向下一个节点（类似于指针）。最后一个节点的Next为null来标识链表的尾。

如下图

代码实现

 1 /* ------------  单链表 ------------- */
 2 //链表头
 3 SingleLink head = new SingleLink();
 4 SingleLink node;
 5  
 6 //添加节点
 7 node = new SingleLink(1, "刘德华");
 8 SingleLink.Add(ref head, node);
 9  
10 node = new SingleLink(2, "张学友");
11 SingleLink.Add(ref head, node);
12  
13 node = new SingleLink(3, "郭富城");
14 SingleLink.Add(ref head, node);
15  
16 node = new SingleLink(4, "黎明");
17 SingleLink.Add(ref head, node);
18  
19  
20 //删除节点
21 SingleLink.Remove(ref head, 2);
22  
23 //遍历所有节点
24 SingleLink cursor = head;
25 while (cursor.Next != null)
26 {
27     Console.WriteLine(cursor.Next.ToString());
28     cursor = cursor.Next;
29 }
30  
31  
32 /// <summary>
33 /// 单链表
34 /// </summary>
35 public class SingleLink
36 {
37     public int No { get; set; }
38  
39     public string Name { get; set; }
40  
41     //指向下一个节点(有点像指针)
42     public SingleLink Next { get; set; }
43  
44     public SingleLink() { }
45  
46     public SingleLink(int no, string name)
47     {
48         this.No = no;
49         this.Name = name;
50     }
51  
52  
53     /// <summary>
54     /// 添加
55     /// </summary>
56     /// <param name="head">链表头</param>
57     /// <param name="addNode">添加节点</param>
58     public static void Add(ref SingleLink head, SingleLink addNode)
59     {
60         SingleLink cursor = head;
61         while (cursor.Next != null)
62         {
63             cursor = cursor.Next;
64         }
65         cursor.Next = addNode;
66     }
67  
68  
69     /// <summary>
70     /// 删除
71     /// </summary>
72     /// <param name="head">链表头</param>
73     /// <param name="no">删除编号</param>
74     public static void Remove(ref SingleLink head, int no)
75     {
76         SingleLink cursor = head;
77         while (cursor.Next !=null)
78         {
79             if (cursor.Next.No == no)
80             {
81                 cursor.Next = cursor.Next.Next;
82                 return;
83             }
84             cursor = cursor.Next;
85         }
86     }
87  
88  
89     /// <summary>
90     /// 输入信息(重写ToString方法)
91     /// </summary>
92     /// <returns></returns>
93     public override string ToString()
94     {
95         return "No---> " + No + "  Name---> " + Name;
96     }
97 }

View Code

代码分析图

双链表

　　双链表的构成：双链表跟单链表差不多，也是必须要有一个链表头（head）,每个节点里面有一个Next，最后一个节点的Next为null来标识链表的尾。只不过双链表在每个节点上面添加一个Prev，来标识当前节点的上一个节点。

如图：

代码实现

  1 /* ------------  双链表 ------------- */
  2 //链表头
  3 DoubleLink head = new DoubleLink();
  4 DoubleLink node;
  5  
  6 //添加节点
  7 node = new DoubleLink(1,"刘德华");
  8 DoubleLink.Add(ref head, node);
  9  
 10 node = new DoubleLink(2, "张学友");
 11 DoubleLink.Add(ref head, node);
 12  
 13 node = new DoubleLink(3, "郭富城");
 14 DoubleLink.Add(ref head, node);
 15  
 16 node = new DoubleLink(4, "黎明");
 17 DoubleLink.Add(ref head, node);
 18  
 19 //删除节点
 20 DoubleLink.Remove(ref head,3);
 21  
 22 //遍历所有节点
 23 DoubleLink cursor = head;
 24 while (cursor.Next != null)
 25 {
 26     Console.WriteLine(cursor.Next.ToString());
 27     cursor = cursor.Next;
 28 }
 29  
 30  
 31 /// <summary>
 32 /// 双链表
 33 /// </summary>
 34 public class DoubleLink
 35 {
 36     public int No { get; set; }
 37  
 38     public string Name { get; set; }
 39  
 40     //下个节点
 41     public DoubleLink Prev { get; set; }
 42  
 43     //上个节点
 44     public DoubleLink Next { get; set; }
 45  
 46     public DoubleLink() { }
 47  
 48     public DoubleLink(int no, string name)
 49     {
 50         this.No = no;
 51         this.Name = name;
 52     }
 53  
 54  
 55     /// <summary>
 56     /// 添加
 57     /// </summary>
 58     /// <param name="head">链表头</param>
 59     /// <param name="addNode"></param>
 60     public static void Add(ref DoubleLink head, DoubleLink addNode)
 61     {
 62         DoubleLink cursor = head;
 63         while (cursor.Next != null)
 64         {
 65             cursor = cursor.Next;
 66         }
 67         cursor.Next = addNode;
 68         cursor.Next.Prev = cursor;
 69     }
 70  
 71  
 72     /// <summary>
 73     /// 删除
 74     /// </summary>
 75     /// <param name="head">链表头</param>
 76     /// <param name="no">删除编号</param>
 77     public static void Remove(ref DoubleLink head, int no)
 78     {
 79         DoubleLink cursor = head.Next;
 80         while (cursor != null)
 81         {
 82             if (cursor.No == no)
 83             {
 84                 //防止是删除最后一个
 85                 if (cursor.Next != null)
 86                 {
 87                     cursor.Next.Prev = cursor.Prev;
 88                 }
 89                 cursor.Prev.Next = cursor.Next;
 90                 return;
 91             }
 92             cursor = cursor.Next;
 93         }
 94     }
 95  
 96  
 97     /// <summary>
 98     /// 输入信息(重写ToString方法)
 99     /// </summary>
100     /// <returns></returns>
101     public override string ToString()
102     {
103         return "No---> " + No + "  Name---> " + Name;
104     }
105 }

View Code

代码分析图

环形链表

　　环形链表是在单链表基础之上把尾指向头就构成了一个环形的链表了。也就是单链表最后一个节点的Next指Head就可以了。

如图：

代码实现

  1 //环形链表
  2 LoopLink head = new LoopLink();
  3 LoopLink node;
  4 
  5 
  6 //添加节点
  7 node = new LoopLink(1, "刘德华");
  8 LoopLink.Add(ref head, node);
  9 
 10 node = new LoopLink(2, "张学友");
 11 LoopLink.Add(ref head, node);
 12 
 13 node = new LoopLink(3, "郭富城");
 14 LoopLink.Add(ref head, node);
 15 
 16 node = new LoopLink(4, "黎明");
 17 LoopLink.Add(ref head, node);
 18 
 19 LoopLink.Remove(ref head, 2);
 20 
 21 //遍历所有节点（遍历需要拿到它的头或者尾来标识链表的结束位置,我是拿到头来遍历的）
 22 LoopLink cursor = head;
 23 LoopLink first = head;
 24 //首先输出头的信息
 25 Console.WriteLine(head);
 26 //遍历所有节点,如果遍历到头节点就退出循环,链表打印完成
 27 while (!Object.ReferenceEquals(cursor.Next, first))
 28 {
 29     Console.WriteLine(cursor.Next.ToString());
 30     cursor = cursor.Next;
 31 }
 32 
 33 
 34 
 35 /// <summary>
 36 /// 环形链表
 37 /// </summary>
 38 class LoopLink
 39 {
 40 
 41     public int No { get; set; }
 42 
 43     public string Name { get; set; }
 44 
 45     public LoopLink Next { get; set; }
 46 
 47     public LoopLink() { }
 48 
 49     public LoopLink(int no, string name)
 50     {
 51         this.No = no;
 52         this.Name = name;
 53     }
 54 
 55     public static LoopLink Cursor { get; set; }
 56 
 57     /// <summary>
 58     /// 添加
 59     /// </summary>
 60     /// <param name="head">链表头</param>
 61     /// <param name="addNode">所要添加节点</param>
 62     public static void Add(ref LoopLink head, LoopLink addNode)
 63     {
 64         if (head.Next == null)
 65         {
 66             head = addNode;
 67             head.Next = addNode;
 68             Cursor = head;
 69         }
 70         else
 71         {
 72             Cursor.Next = addNode;
 73             addNode.Next = head;
 74             Cursor = Cursor.Next;
 75         }
 76     }
 77 
 78 
 79     /// <summary>
 80     /// 删除节点
 81     /// </summary>
 82     /// <param name="head">链表头</param>
 83     /// <param name="no">所要删除编号</param>
 84     public static void Remove(ref LoopLink head, int no)
 85     {
 86         LoopLink cur = head;
 87 
 88         while (true)
 89         {
 90             if (cur.Next.No == no)
 91             {
 92                 cur.Next = cur.Next.Next;
 93                 return;
 94             }
 95             cur = cur.Next;
 96         }
 97     }
 98 
 99 
100     /// <summary>
101     /// 输入信息(重写ToString方法)
102     /// </summary>
103     /// <returns></returns>
104     public override string ToString()
105     {
106         return "No---> " + No + "  Name---> " + Name;
107     }
108 }

View Code

扩展训练(面试题)

　　题目：有一颗炸弹，有N个人围成一个圆形，从第K个人开始数数，数M就退出圆。最后算出留下来要被炸死是第几个人。请用代码实现。

　　代码如下：

  1 //N个人
  2 int n = 5;
  3 
  4 //第K个人开始数数
  5 int k = 3;
  6 
  7 //数到M就退出
  8 int m = 4;
  9 
 10 Game head = new Game();
 11 
 12 //构建一个由N个人组成的圆形
 13 Game.Add(ref head, n);
 14 //查找谁会被炸死
 15 Game.Bomb(ref head, k, m);
 16 
 17 
 18 
 19 /// <summary>
 20 /// 游戏类
 21 /// </summary>
 22 public class Game
 23 {
 24     public int No { get; set; }
 25 
 26     public Game Next { get; set; }
 27 
 28     public Game() { }
 29 
 30     public Game(int no)
 31     {
 32         this.No = no;
 33     }
 34 
 35 
 36     public static void Add(ref Game head, int n)
 37     {
 38         Game cursor = null;
 39         for (int i = 0; i < n; i++)
 40         {
 41             Game temp = new Game(i+1);
 42             if (i == 0)
 43             {
 44                 head.Next