链表的概念以及链表与数组的差异不做过多的叙述,相信大家都耳熟能详,这里以c#语言实现简单的双向链表,作为备用,记录下~
public class Node<T> { private Node<T> prev; private Node<T> next; private T val; public Node<T> Prev { get { return prev; } set { prev = value; } } public Node<T> Next { get { return next; } set { next = value; } } public T Data { get { return val; } set { val = value; } } public Node(T item) { val = item; } }
public class Link<T>{ public Node<T> head { get; set; } public int count { get; set; } public Link() { Node<T> node = new Node<T>(default(T)); node.Next = node; node.Prev = node; head = node; count++; } public Node<T> Append(T node) { Node<T> newNode = new Node<T>(node); newNode.Prev = head.Prev; newNode.Next = head; head.Prev.Next = newNode; head.Prev = newNode; count++; return newNode; } public Node<T> Insert(int index, T node) { if (index < 0 || index > count) throw new IndexOutOfRangeException("索引超出界限"); if (index == 0) return Append(node); else { Node<T> bnode = Get(index); Node<T> newNode = new Node<T>(node); bnode.Prev.Next = newNode; newNode.Prev = bnode.Prev; newNode.Next = bnode; bnode.Prev = newNode; count++; return newNode; } } public void Delete(int index) { if (index < 0 || index > count) throw new IndexOutOfRangeException("索引超出界限"); Node<T> node = Get(index); node.Prev.Next = node.Next; node.Next.Prev = node.Prev; count--; } public void showAll() { for (int i = 0; i < count; i++) { Console.WriteLine($"index:{i},content:{Get(i).Data}"); } } public Node<T> Get(int index) { if (index < 0 || index >= count) throw new IndexOutOfRangeException("索引超出界限"); //如果要找的节点在前半部分,则顺序查找, if (index < count / 2) { var node = head.Next; for (int i = 0; i < index; i++) node = node.Next; return node; } //否则逆序查找 var preNode = head.Prev; for (int i = 0; i < count-1-index; i++) preNode = preNode.Prev; return preNode; } /// <summary> /// 获取最后一条 /// </summary> /// <returns></returns> public Node<T> GetLast() { return Get(count - 1); } public Node<T> GetFirst() { return Get(0); } }
测试:
class Program { static void Main(string[] args) { Link<string> dlink = new Link<string>(); dlink.Append("我是第一位"); dlink.Append("我是第二位"); dlink.Append("我是第三位"); dlink.Insert(2,"我是第四位,我占用了第二的位置"); dlink.Append("我是第五位"); dlink.Append("我是第六位"); dlink.Append("我是第七位"); dlink.Append("我是第八位"); dlink.Append("我是第九位"); dlink.Delete(7); dlink.showAll(); Console.ReadLine(); } }
打印输出结果:
欢迎一起学习交流