赞
踩
说明:C#有自己封装的双向循环链表LinkedList<>,足以满足日常工作需要。这里只是学习数据结构“单链表”的手搓代码,理解精神即可。
PS:这篇文章第一版写的有点烂,这是第二版,好看点。
PSS: 本文的重点是代码代码代码!而不是数据结构的一些基础概念和分类;
完全没接触过的同学,可以去看B站王卓教授的视频。
说明:
- 如图,链表第一个元素是0031,即“赵”,赵的下一个是0007,即“钱”,钱的下一个是0013,即“孙”,依此类推。
- 物理上这些地址连续吗?很明显,不连续。
- 物理次序和逻辑次序有关系嘛?很明显,没关系。赵是第一个,物理地址却在其他元素的下面。
说明: 比如说你有a2的引用,你可以拿到a3,但你拿不到a1。
说明: 比如说你有a2的引用,你可以拿到a3,而且你也能拿到a1。
namespace YoyoCode { internal class SinglyLinkedList<T> { //首元结点 public SinglyLinkedListNode<T> First; //尾结点 public SinglyLinkedListNode<T> Last; //结点数量 public int NodeCount = 0; /// <summary> /// 是否为空 /// </summary> /// <returns>bool,链表是否为空</returns> public bool IsEmpty() { return NodeCount == 0 ? true : false; } /// <summary> /// 清空链表 /// </summary> public void Clear() { First = null; Last = null; NodeCount = 0; } /// <summary> /// 头插法 /// </summary> /// <param name="value">类型为T的值</param> public void AddFirst(T value) { SinglyLinkedListNode<T> node = new SinglyLinkedListNode<T>(value); if (IsEmpty()) { First = node; Last = node; } else { node.Next= First; First= node; } NodeCount++; } /// <summary> /// 尾插法 /// </summary> /// <param name="value">类型为T的值</param> public void AddLast(T value) { SinglyLinkedListNode<T> node = new SinglyLinkedListNode<T>(value); if (IsEmpty()) { First = node; Last = node; } else { Last.Next = node; Last = node; } NodeCount++; } /// <summary> /// 在对应的索引插入元素 /// </summary> /// <param name="idx">索引,从0开始</param> public bool AddAt(T value, int idx) { if (idx < 0 || idx > NodeCount) { return false; } if (idx == 0) { AddFirst(value); return true; } if (idx == NodeCount) { AddLast(value); return true; } //其他情况 SinglyLinkedListNode<T> prev = First; SinglyLinkedListNode<T> cur = First.Next; SinglyLinkedListNode<T> node = new SinglyLinkedListNode<T>(value); for (int i = 1; i < idx; i++) { prev = prev.Next; cur = cur.Next; } prev.Next = node; node.Next = cur; NodeCount ++; return true; } /// <summary> /// 删除第一个元素 /// </summary> /// <returns>bool,是否删除成功</returns> public bool RemoveFirst() { if (IsEmpty()) { return false; } //链表只有一个元素 if (NodeCount > 1 ) { First = First.Next; } else { First = null; Last = null; } NodeCount--; return true; } /// <summary> /// 删除对应索引的元素 /// </summary> /// <returns>bool,是否删除成功</returns> public bool RemoveAt(int idx) { if (IsEmpty()) { return false; } if (idx == 0) { return RemoveFirst(); } SinglyLinkedListNode<T> prev = First; SinglyLinkedListNode<T> cur = First.Next; for (int i = 1; i < idx; i++) { prev = prev.Next; cur = cur.Next; } if (idx == NodeCount - 1) { Last = prev; prev.Next = null; } else { prev.Next = cur.Next; } NodeCount--; return true; } /// <summary> /// 删除最后一个元素 /// </summary> /// <returns>bool,是否删除成功</returns> public bool RemoveLast() { return RemoveAt(NodeCount - 1); } } /// <summary> /// 单向链表中的结点数据结构 /// </summary> internal class SinglyLinkedListNode<T> { public T data; public SinglyLinkedListNode<T> Next; public SinglyLinkedListNode(T data) { this.data = data; } } }
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using System.Threading.Tasks; namespace YoyoCode { internal class DoubleLinkedList<T> { //首元结点 public DoubleLinkedListNode<T> First; //尾结点 public DoubleLinkedListNode<T> Last; //结点数量 public int NodeCount = 0; /// <summary> /// 是否为空 /// </summary> /// <returns>bool,链表是否为空</returns> public bool IsEmpty() { return NodeCount == 0 ? true : false; } /// <summary> /// 清空链表 /// </summary> public void Clear() { First = null; Last = null; NodeCount = 0; } /// <summary> /// 头插法 /// </summary> /// <param name="value">类型为T的值</param> public void AddFirst(T value) { DoubleLinkedListNode<T> node = new DoubleLinkedListNode<T>(value); if (IsEmpty()) { First = node; Last = node; } else { node.Next = First; First.Prev = node; First = node; } NodeCount++; } /// <summary> /// 尾插法 /// </summary> /// <param name="value">类型为T的值</param> public void AddLast(T value) { DoubleLinkedListNode<T> node = new DoubleLinkedListNode<T>(value); if (IsEmpty()) { First = node; Last = node; } else { Last.Next = node; node.Prev= Last; Last = node; } NodeCount++; } /// <summary> /// 在对应的索引插入元素 /// </summary> /// <param name="idx">索引,从0开始</param> public bool AddAt(T value, int idx) { if (idx < 0 || idx > NodeCount) { return false; } if (idx == 0) { AddFirst(value); return true; } if (idx == NodeCount) { AddLast(value); return true; } //其他情况 DoubleLinkedListNode<T> prev = First; DoubleLinkedListNode<T> cur = First.Next; DoubleLinkedListNode<T> node = new DoubleLinkedListNode<T>(value); for (int i = 1; i < idx; i++) { prev = prev.Next; cur = cur.Next; } prev.Next = node; node.Prev = prev; node.Next = cur; cur.Prev= node; NodeCount++; return true; } /// <summary> /// 删除第一个元素 /// </summary> /// <returns>bool,是否删除成功</returns> public bool RemoveFirst() { if (IsEmpty()) { return false; } //链表是否只有一个元素 if (NodeCount > 1) { First.Next.Prev = null; First = First.Next; } else { First = null; Last = null; } NodeCount--; return true; } /// <summary> /// 删除对应索引的元素 /// </summary> /// <returns>bool,是否删除成功</returns> public bool RemoveAt(int idx) { if (IsEmpty()) { return false; } if (idx == 0) { return RemoveFirst(); } DoubleLinkedListNode<T> prev = First; DoubleLinkedListNode<T> cur = First.Next; for (int i = 1; i < idx; i++) { prev = prev.Next; cur = cur.Next; } if (idx == NodeCount - 1) { Last = prev; prev.Next = null; } else { prev.Next = cur.Next; prev.Next.Prev = prev; } NodeCount--; return true; } /// <summary> /// 删除最后一个元素 /// </summary> /// <returns>bool,是否删除成功</returns> public bool RemoveLast() { return RemoveAt(NodeCount - 1); } } /// <summary> /// 双向链表中的结点数据结构 /// </summary> internal class DoubleLinkedListNode<T> { public T data; public DoubleLinkedListNode<T> Next; public DoubleLinkedListNode<T> Prev; public DoubleLinkedListNode(T data) { this.data = data; } } }
说明:
- 同比单向链表,多了一个Prev指针指向了上一个元素而已。
- 在处理删除、插入操作时,需要额外注意Prev指针的赋值即可。
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using System.Threading.Tasks; namespace YoyoCode { internal class CircularSLinkedList<T> { //尾结点 public SinglyLinkedListNode<T> Last; //结点数量 public int NodeCount = 0; /// <summary> /// 是否为空 /// </summary> /// <returns>bool,链表是否为空</returns> public bool IsEmpty() { return NodeCount == 0 ? true : false; } /// <summary> /// 清空链表 /// </summary> public void Clear() { Last = null; NodeCount = 0; } /// <summary> /// 头插法 /// </summary> /// <param name="value">类型为T的值</param> public void AddFirst(T value) { SinglyLinkedListNode<T> node = new SinglyLinkedListNode<T>(value); if (IsEmpty()) { Last = node; Last.Next = Last; } else { node.Next = Last.Next; Last.Next = node; } NodeCount++; } /// <summary> /// 尾插法 /// </summary> /// <param name="value">类型为T的值</param> public void AddLast(T value) { SinglyLinkedListNode<T> node = new SinglyLinkedListNode<T>(value); if (IsEmpty()) { Last = node; Last.Next = Last; } else { Last.Next = node; Last = node; } NodeCount++; } /// <summary> /// 在对应的索引插入元素 /// </summary> /// <param name="idx">索引,从0开始</param> public bool AddAt(T value, int idx) { if (idx < 0 || idx > NodeCount) { return false; } if (idx == 0) { AddFirst(value); return true; } if (idx == NodeCount) { AddLast(value); return true; } //其他情况 SinglyLinkedListNode<T> prev = Last.Next; SinglyLinkedListNode<T> cur = Last.Next.Next; SinglyLinkedListNode<T> node = new SinglyLinkedListNode<T>(value); for (int i = 1; i < idx; i++) { prev = prev.Next; cur = cur.Next; } prev.Next = node; node.Next = cur; NodeCount++; return true; } /// <summary> /// 删除第一个元素 /// </summary> /// <returns>bool,是否删除成功</returns> public bool RemoveFirst() { if (IsEmpty()) { return false; } //链表只有一个元素 if (NodeCount > 1) { Last.Next = Last.Next.Next; } else { Last = null; } NodeCount--; return true; } /// <summary> /// 删除对应索引的元素 /// </summary> /// <returns>bool,是否删除成功</returns> public bool RemoveAt(int idx) { if (IsEmpty()) { return false; } if (idx == 0) { return RemoveFirst(); } SinglyLinkedListNode<T> prev = Last.Next; SinglyLinkedListNode<T> cur = Last.Next.Next; for (int i = 1; i < idx; i++) { prev = prev.Next; cur = cur.Next; } if (idx == NodeCount - 1) { prev.Next = Last.Next; Last = prev; } else { prev.Next = cur.Next; } NodeCount--; return true; } /// <summary> /// 删除最后一个元素 /// </summary> /// <returns>bool,是否删除成功</returns> public bool RemoveLast() { return RemoveAt(NodeCount - 1); } } }
说明:
- 同比单向链表,不需要First指针了。
- 在处理头尾的删除、插入操作时,需要额外注意Last指针中Next指针的赋值即可。
- Last.Next实际上就是First,因为可以通过Last直接找到First,所以删除掉了。即尾指针的Next指向了链表的第一个元素,形成了一个环。
结语:
诶?是不是想问为啥我突然弄数据结构了?
诶!面试两家都在数据结构和算法这儿碰壁了,淦。。。
咱就是说,工作了两年半(bushi),基本没用到过什么堆排、快排、二叉树什么的,但人家就是问了。。。
我也很绝望啊!于谦:那怎么办?当然是肝了哈哈哈哈,线性表两天肝完了顺序表+单链表的原理和相应增删改查算法。
加油!!!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。