Реализовать двусвязный список - C#
Формулировка задачи:
Ребята, помогите, пожалуйста, реализовать простейший двусвязный список. Никак не могу понять, как его сделать на С#. Или подкиньте какую-нибудь хорошую литературу по этой теме.
Решение задачи: «Реализовать двусвязный список»
textual
Листинг программы
internal class DoubleLinkedList<T> : IEnumerable, IMyMethodSignatureInterface<T> { #region Поля, индексатор, свойство private NodeDoubleLinkedList<T> _head; private NodeDoubleLinkedList<T> _tail; // счетчик списка private int Count { get; set; } public T this[int index] { get { if (index < 0) throw new ArgumentOutOfRangeException(); NodeDoubleLinkedList<T> current = _head; for (int i = 0; i < index; i++) { if (current.Next == null) throw new ArgumentOutOfRangeException(); current = current.Next; } return current.Value; } } // индексатор private bool IsEmpty { get { { return _head == null; } } } // своство проверка содержит ли список какой либо элемент #endregion #region Реализация методов public void AddFirst(T value) { NodeDoubleLinkedList<T> node = new NodeDoubleLinkedList<T>(value); NodeDoubleLinkedList<T> temp = _head; _head = node; // указание на новое начало списка _head.Next = node; // устанавливаем указатель на след за хедом узел _head.Next = temp; // устанавливаем указатель. if (Count == 0) { _tail = _head; } else { temp.Previous = _head; } Count++; } public void AddLast(T value) { NodeDoubleLinkedList<T> node = new NodeDoubleLinkedList<T>(value); if (Count == 0) { _head = node; } else { _tail.Next = node; // делаем резервное место под след значение node.Previous = _tail; // кидаем указатель хвоста на пред элемент перед добавленым } _tail = node; // новый конец списка Count++; } public void AddInside(T value, int index) // вставка в середину { if (index > Count || index < 0) throw new ArgumentOutOfRangeException(); if (index == 0) AddFirst(value); else if (index == (Count - 1)) AddLast(value); else { NodeDoubleLinkedList<T> currentNode = _head; for (int i = 0; i < index - 1; i++) { currentNode = currentNode.Next; } NodeDoubleLinkedList<T> node = new NodeDoubleLinkedList<T>(value, currentNode.Next); currentNode.Next = node; Count++; } } public void Remove(T value) { NodeDoubleLinkedList<T> previous = null; NodeDoubleLinkedList<T> current = _head; // первый узел заносим while (current != null) { if (current.Value.Equals(value)) { // Узел находится в середине или в конце списка if (previous != null) // если предыдущий пустой, то удаляем первый. { previous.Next = current.Next; // убираем указатель между удаляющим элементом // Если это последний элемент списка - обновить _tail if (current.Next == null) { _tail = previous; } else { current.Next.Previous = previous; // указатель со след элемента на предыдущий перед удаляемый } Count--; } else { RemoveFirst(); } } previous = current; current = current.Next; } } public T RemoveAt(int index) { if (index > Count || index < 0) throw new ArgumentOutOfRangeException(); T removedData; if (index == 0) removedData = RemoveFirst(); else if (index == (Count - 1)) removedData = RemoveLast(); else { NodeDoubleLinkedList<T> current = _head; for (int i = 0; i < index - 1; i++) { current = current.Next; } removedData = current.Value; current.Next = current.Next.Next; Count--; } return removedData; } // удаление по индексу начиная с 0. public T RemoveFirst() { T removedData = _head.Value; if (Count != 0) { _head = _head.Next; Count--; if (Count == 0) { _tail = null; } else { _head.Previous = null; } } Count--; return removedData; } public T RemoveLast() { T removedData = _tail.Value; switch (Count) { case 0: return removedData; case 1: _head = _tail = null; break; default: _tail.Previous.Next = null; _tail = _tail.Previous; break; } Count--; return removedData; } public int FindIdByElement(T value) // номер элемента по значению { NodeDoubleLinkedList<T> current = _head; for (int i = 0; i < Count; i++) { if (current.Value.Equals(value)) Console.WriteLine("Поиск нужного элемента имеет номер {0} в списке", i); current = current.Next; } // нету в списке return -1; } public void Replace(T oldItem, T newItem) // замена определенного элемента { NodeDoubleLinkedList<T> current = _head; while (current != null) { if (current.Value.Equals(oldItem)) { current.Value = newItem; } current = current.Next; } } public void ReplaceLast(T value) { NodeDoubleLinkedList<T> node = new NodeDoubleLinkedList<T>(value); if (_head == null) { _head = node; _tail = node; } else { _tail.Value = value; } } // замена в конце public void ReplaceFirst(T value) { NodeDoubleLinkedList<T> node = new NodeDoubleLinkedList<T>(value); if (_head == null) { _head = node; _tail = node; } else { _head.Value = value; } } public void ClearAll() // очистка всего списка { _head = null; _tail = null; Count = 0; } public void Sum() { // юзаем динамическую типизацию. с# 4.0 ficha dynamic sum = 0; NodeDoubleLinkedList<T> temp = _head; while (temp != null) { sum += temp.Value; temp = temp.Next; } //Console.WriteLine("Sum of the List Elements: {0} ", sum); } // Подсчет суммы всех элементов связного списка #endregion #region Реализация интерфейса IEnumerable // Возвращает экземпляр интерфейса IEnumerator <T>, который позволяет пронумеровать элементы списка public IEnumerator<T> GetEnumerator() { NodeDoubleLinkedList<T> current = _head; while (current != null) { yield return current.Value; current = current.Next; } } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } #endregion } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д