代码拉取完成,页面将自动刷新
using System;
using System.Collections.Generic;
using Utilities.Exceptions;
namespace DataStructures.LinkedList.DoublyLinkedList;
/// <summary>
/// Similar to a Singly Linked List but each node contains a refenrence to the previous node in the list.
/// <see cref="System.Collections.Generic.LinkedList{T}" /> is a doubly linked list.
/// Compared to singly linked lists it can be traversed forwards and backwards.
/// Adding a node to a doubly linked list is simpler because ever node contains a reference to the previous node.
/// </summary>
/// <typeparam name="T">Generic type.</typeparam>
public class DoublyLinkedList<T>
{
/// <summary>
/// Initializes a new instance of the <see cref="DoublyLinkedList{T}" /> class.
/// </summary>
/// <param name="data"> Data of the original head of the list.</param>
public DoublyLinkedList(T data)
{
Head = new DoublyLinkedListNode<T>(data);
Tail = Head;
Count = 1;
}
/// <summary>
/// Initializes a new instance of the <see cref="DoublyLinkedList{T}" /> class from an enumerable.
/// </summary>
/// <param name="data"> Enumerable of data to be stored in the list.</param>
public DoublyLinkedList(IEnumerable<T> data)
{
foreach (var d in data)
{
Add(d);
}
}
/// <summary>
/// Gets the amount of nodes in the list.
/// </summary>
public int Count { get; private set; }
/// <summary>
/// Gets or sets the first node of the list.
/// </summary>
private DoublyLinkedListNode<T>? Head { get; set; }
/// <summary>
/// Gets or sets the last node of the list.
/// </summary>
private DoublyLinkedListNode<T>? Tail { get; set; }
/// <summary>
/// Replaces the Head of the list with the new value.
/// </summary>
/// <param name="data"> Value for the new Head of the list.</param>
/// <returns>The new Head node.</returns>
public DoublyLinkedListNode<T> AddHead(T data)
{
var node = new DoublyLinkedListNode<T>(data);
if (Head is null)
{
Head = node;
Tail = node;
Count = 1;
return node;
}
Head.Previous = node;
node.Next = Head;
Head = node;
Count++;
return node;
}
/// <summary>
/// Adds a new value at the end of the list.
/// </summary>
/// <param name="data"> New value to be added to the list.</param>
/// <returns>The new node created based on the new value.</returns>
public DoublyLinkedListNode<T> Add(T data)
{
if (Head is null)
{
return AddHead(data);
}
var node = new DoublyLinkedListNode<T>(data);
Tail!.Next = node;
node.Previous = Tail;
Tail = node;
Count++;
return node;
}
/// <summary>
/// Adds a new value after an existing node.
/// </summary>
/// <param name="data"> New value to be added to the list.</param>
/// <param name="existingNode"> An existing node in the list.</param>
/// <returns>The new node created based on the new value.</returns>
public DoublyLinkedListNode<T> AddAfter(T data, DoublyLinkedListNode<T> existingNode)
{
if (existingNode == Tail)
{
return Add(data);
}
var node = new DoublyLinkedListNode<T>(data);
node.Next = existingNode.Next;
node.Previous = existingNode;
existingNode.Next = node;
if (node.Next is not null)
{
node.Next.Previous = node;
}
Count++;
return node;
}
/// <summary>
/// Gets an enumerable based on the data in the list.
/// </summary>
/// <returns>The data in the list in an IEnumerable. It can used to create a list or an array with LINQ.</returns>
public IEnumerable<T> GetData()
{
var current = Head;
while (current is not null)
{
yield return current.Data;
current = current.Next;
}
}
/// <summary>
/// Gets an enumerable based on the data in the list reversed.
/// </summary>
/// <returns>The data in the list in an IEnumerable. It can used to create a list or an array with LINQ.</returns>
public IEnumerable<T> GetDataReversed()
{
var current = Tail;
while (current is not null)
{
yield return current.Data;
current = current.Previous;
}
}
/// <summary>
/// Reverses the list. Because of how doubly linked list are structured this is not a complex action.
/// </summary>
public void Reverse()
{
var current = Head;
DoublyLinkedListNode<T>? temp = null;
while (current is not null)
{
temp = current.Previous;
current.Previous = current.Next;
current.Next = temp;
current = current.Previous;
}
Tail = Head;
// temp can be null on empty list
if (temp is not null)
{
Head = temp.Previous;
}
}
/// <summary>
/// Looks for a node in the list that contains the value of the parameter.
/// </summary>
/// <param name="data"> Value to be looked for in a node.</param>
/// <returns>The node in the list the has the paramater as a value or null if not found.</returns>
public DoublyLinkedListNode<T> Find(T data)
{
var current = Head;
while (current is not null)
{
if (current.Data is null && data is null || current.Data is not null && current.Data.Equals(data))
{
return current;
}
current = current.Next;
}
throw new ItemNotFoundException();
}
/// <summary>
/// Looks for a node in the list that contains the value of the parameter.
/// </summary>
/// <param name="position"> Position in the list.</param>
/// <returns>The node in the list the has the paramater as a value or null if not found.</returns>
/// <exception cref="ArgumentOutOfRangeException">Thrown when position is negative or out range of the list.</exception>
public DoublyLinkedListNode<T> GetAt(int position)
{
if (position < 0 || position >= Count)
{
throw new ArgumentOutOfRangeException($"Max count is {Count}");
}
var current = Head;
for (var i = 0; i < position; i++)
{
current = current!.Next;
}
return current ?? throw new ArgumentOutOfRangeException($"{nameof(position)} must be an index in the list");
}
/// <summary>
/// Removes the Head and replaces it with the second node in the list.
/// </summary>
public void RemoveHead()
{
if (Head is null)
{
throw new InvalidOperationException();
}
Head = Head.Next;
if (Head is null)
{
Tail = null;
Count = 0;
return;
}
Head.Previous = null;
Count--;
}
/// <summary>
/// Removes the last node in the list.
/// </summary>
public void Remove()
{
if (Tail is null)
{
throw new InvalidOperationException("Cannot prune empty list");
}
Tail = Tail.Previous;
if (Tail is null)
{
Head = null;
Count = 0;
return;
}
Tail.Next = null;
Count--;
}
/// <summary>
/// Removes specific node.
/// </summary>
/// <param name="node"> Node to be removed.</param>
public void RemoveNode(DoublyLinkedListNode<T> node)
{
if (node == Head)
{
RemoveHead();
return;
}
if (node == Tail)
{
Remove();
return;
}
if (node.Previous is null || node.Next is null)
{
throw new ArgumentException(
$"{nameof(node)} cannot have Previous or Next null if it's an internal node");
}
node.Previous.Next = node.Next;
node.Next.Previous = node.Previous;
Count--;
}
/// <summary>
/// Removes a node that contains the data from the parameter.
/// </summary>
/// <param name="data"> Data to be removed form the list.</param>
public void Remove(T data)
{
var node = Find(data);
RemoveNode(node);
}
/// <summary>
/// Looks for the index of the node with the parameter as data.
/// </summary>
/// <param name="data"> Data to look for.</param>
/// <returns>Returns the index of the node if it is found or -1 if the node is not found.</returns>
public int IndexOf(T data)
{
var current = Head;
var index = 0;
while (current is not null)
{
if (current.Data is null && data is null || current.Data is not null && current.Data.Equals(data))
{
return index;
}
index++;
current = current.Next;
}
return -1;
}
/// <summary>
/// List contains a node that has the parameter as data.
/// </summary>
/// <param name="data"> Node to be removed.</param>
/// <returns>True if the node is found. False if it isn't.</returns>
public bool Contains(T data) => IndexOf(data) != -1;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。