zergon321

Single-linked list

Jul 24th, 2021
868
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2.  
  3. namespace Lists
  4. {
  5.     /// <summary>
  6.     /// Односвязный список.
  7.     /// </summary>
  8.     /// <typeparam name="T">Тип элемента, хранящегося в списке.</typeparam>
  9.     public class SingleLinkedList<T>
  10.     {
  11.         int length;
  12.         Node<T> head;
  13.         Node<T> end;
  14.  
  15.         /// <summary>
  16.         /// Возвращает начальный элемент списка.
  17.         /// </summary>
  18.         /// <returns>Значение начального элемента списка.</returns>
  19.         public T Head()
  20.         {
  21.             return head.Elem();
  22.         }
  23.  
  24.         /// <summary>
  25.         /// Возвращает конечный элемент списка.
  26.         /// </summary>
  27.         /// <returns>Значение конечного элемента списка.</returns>
  28.         public T End()
  29.         {
  30.             return end.Elem();
  31.         }
  32.  
  33.         /// <summary>
  34.         /// Возвращает длину списка.
  35.         /// </summary>
  36.         /// <returns>Длина списка.</returns>
  37.         public int Length()
  38.         {
  39.             return length;
  40.         }
  41.  
  42.         /// <summary>
  43.         /// Вставляет элемент в начало списка.
  44.         /// </summary>
  45.         /// <param name="elem">Элемент для вставки.</param>
  46.         public void AddToHead(T elem)
  47.         {
  48.             Node<T> node = new Node<T>(elem, null);
  49.  
  50.             if (head == null)
  51.             {
  52.                 end = node;
  53.             }
  54.             else
  55.             {
  56.                 node.SetNext(head);
  57.             }
  58.  
  59.             head = node;
  60.             length++;
  61.  
  62.             return;
  63.         }
  64.  
  65.         /// <summary>
  66.         /// Вставляет элемент в конец списка.
  67.         /// </summary>
  68.         /// <param name="elem">Элемент для вставки.</param>
  69.         public void AddToTail(T elem)
  70.         {
  71.             Node<T> node = new Node<T>(elem, null);
  72.  
  73.             end.SetNext(node);
  74.             end = node;
  75.             length++;
  76.         }
  77.  
  78.         /// <summary>
  79.         /// Вставляет элемент на указанную позицию.
  80.         /// </summary>
  81.         /// <param name="index">Позиция для вставки.</param>
  82.         /// <param name="elem">Элемент для вставки.</param>
  83.         public void AddByIndex(int index, T elem)
  84.         {
  85.             if (index < 0 || index > length)
  86.             {
  87.                 throw new IndexOutOfRangeException();
  88.             }
  89.  
  90.             if (index == 0)
  91.             {
  92.                 AddToHead(elem);
  93.                 return;
  94.             }
  95.  
  96.             if (index == length)
  97.             {
  98.                 AddToTail(elem);
  99.                 return;
  100.             }
  101.  
  102.             // Найти ноду по индексу.
  103.             int i = 0;
  104.             Node<T> indNode = null;
  105.             Node<T> beforeIndNode = null;
  106.  
  107.             for (Node<T> current = head; current != null; current = current.Next())
  108.             {
  109.                 if (i == index)
  110.                 {
  111.                     indNode = current;
  112.                     break;
  113.                 }
  114.  
  115.                 beforeIndNode = current;
  116.                 i++;
  117.             }
  118.  
  119.             Node<T> node = new Node<T>(elem, indNode);
  120.             beforeIndNode.SetNext(node);
  121.             length++;
  122.         }
  123.  
  124.         /// <summary>
  125.         /// Удаляет элемент в начале списка.
  126.         /// </summary>
  127.         /// <returns>Значение удалённого элемента.</returns>
  128.         public T RemoveHead()
  129.         {
  130.             T elem = head.Elem();
  131.  
  132.             head = head.Next();
  133.             length--;
  134.  
  135.             return elem;
  136.         }
  137.  
  138.         /// <summary>
  139.         /// Удаляет элемент в конце списка.
  140.         /// </summary>
  141.         /// <returns>Значение удалённого элемента.</returns>
  142.         public T RemoveEnd()
  143.         {
  144.             if (length == 1)
  145.             {
  146.                 T _elem = head.Elem();
  147.  
  148.                 head = null;
  149.                 end = null;
  150.  
  151.                 return _elem;
  152.             }
  153.  
  154.             // Найти ноду перед конечной.
  155.             Node<T> beforeEnd = null;
  156.  
  157.             for (Node<T> current = head; current.Next() != null; current = current.Next())
  158.             {
  159.                 beforeEnd = current;
  160.             }
  161.  
  162.             T elem = end.Elem();
  163.  
  164.             beforeEnd.SetNext(null);
  165.             end = beforeEnd;
  166.             length--;
  167.  
  168.             return elem;
  169.         }
  170.  
  171.         /// <summary>
  172.         /// Удаляет элемент в указанной позиции списка.
  173.         /// </summary>
  174.         /// <param name="index">Похиция элемента.</param>
  175.         /// <returns>Значение удалённого элемента.</returns>
  176.         public T RemoveByIndex(int index)
  177.         {
  178.             if (index < 0 || index > length - 1)
  179.             {
  180.                 throw new IndexOutOfRangeException();
  181.             }
  182.  
  183.             if (index == 0)
  184.             {
  185.                 return RemoveHead();
  186.             }
  187.  
  188.             if (index == length - 1)
  189.             {
  190.                 return RemoveEnd();
  191.             }
  192.  
  193.             // Найти ноду по индексу.
  194.             int i = 0;
  195.             Node<T> indNode = null;
  196.             Node<T> beforeIndNode = null;
  197.  
  198.             for (Node<T> current = head; current.Next() != null; current = current.Next())
  199.             {
  200.                 if (i == index)
  201.                 {
  202.                     indNode = current;
  203.                     break;
  204.                 }
  205.  
  206.                 beforeIndNode = current;
  207.                 i++;
  208.             }
  209.  
  210.             T elem = indNode.Elem();
  211.  
  212.             beforeIndNode.SetNext(indNode.Next());
  213.             indNode.SetNext(null);
  214.             length--;
  215.  
  216.             return elem;
  217.         }
  218.  
  219.         /// <summary>
  220.         /// Возвращает значение элементу, расположенного в указанной позиции.
  221.         /// </summary>
  222.         /// <param name="index">Позиция эелемента.</param>
  223.         /// <returns>Значение элемента.</returns>
  224.         public T GetElemByIndex(int index)
  225.         {
  226.             if (index < 0 || index > length - 1)
  227.             {
  228.                 throw new IndexOutOfRangeException();
  229.             }
  230.  
  231.             // Найти ноду по индексу.
  232.             int i = 0;
  233.             Node<T> indNode = null;
  234.  
  235.             for (Node<T> current = head; current != null; current = current.Next())
  236.             {
  237.                 if (i == index)
  238.                 {
  239.                     indNode = current;
  240.                     break;
  241.                 }
  242.  
  243.                 i++;
  244.             }
  245.  
  246.             return indNode.Elem();
  247.         }
  248.  
  249.         /// <summary>
  250.         /// Возвращает набор элементов списка.
  251.         /// </summary>
  252.         /// <returns>Набор элементов списка.</returns>
  253.         public T[] GetElems()
  254.         {
  255.             T[] arr = new T[length];
  256.             int i = 0;
  257.  
  258.             for (Node<T> current = head; current != null; current = current.Next())
  259.             {
  260.                 arr[i] = current.Elem();
  261.                 i++;
  262.             }
  263.  
  264.             return arr;
  265.         }
  266.  
  267.         /// <summary>
  268.         /// Применить указанную процедуру к каждому элементу списка.
  269.         /// </summary>
  270.         /// <param name="visitor">Процедура для применения к элементам списка.</param>
  271.         public void Visit(Action<int, T> visitor)
  272.         {
  273.             int i = 0;
  274.  
  275.             for (Node<T> current = head; current != null; current = current.Next())
  276.             {
  277.                 visitor(i, current.Elem());
  278.                 i++;
  279.             }
  280.         }
  281.     }
  282.  
  283.     /// <summary>
  284.     /// Элемент односвязного списка.
  285.     /// </summary>
  286.     /// <typeparam name="T">Тип элемента списка.</typeparam>
  287.     public class Node<T>
  288.     {
  289.         T elem;
  290.         Node<T> next;
  291.  
  292.         /// <summary>
  293.         /// Конструктор.
  294.         /// </summary>
  295.         /// <param name="elem">Значение элемента.</param>
  296.         /// <param name="next">Указатель на следующий элемент.</param>
  297.         public Node(T elem, Node<T> next)
  298.         {
  299.             this.elem = elem;
  300.             this.next = next;
  301.         }
  302.  
  303.         /// <summary>
  304.         /// Возвращает значение элемента списка.
  305.         /// </summary>
  306.         /// <returns>Значение элемента списка.</returns>
  307.         public T Elem()
  308.         {
  309.             return elem;
  310.         }
  311.  
  312.         /// <summary>
  313.         /// Возвращает следующий за данным элемент списка.
  314.         /// </summary>
  315.         /// <returns>Элемент списка.</returns>
  316.         public Node<T> Next()
  317.         {
  318.             return next;
  319.         }
  320.  
  321.         /// <summary>
  322.         /// Назначает следующий элемент для данного элемента списка.
  323.         /// </summary>
  324.         /// <param name="node">Следующий элемент списка.</param>
  325.         public void SetNext(Node<T> node)
  326.         {
  327.             next = node;
  328.         }
  329.     }
  330. }
RAW Paste Data