Удаление связанных узлов списка


У меня есть этот код, чтобы удалить узлы в связанном списке, которые имеют нечетные значения. Это хорошо работает, но я хочу настроить его для более удобного чтения. Вы можете, пожалуйста, предложить улучшения?

public class MyLinkedList
{
    public int data;
    public MyLinkedList next;

    public MyLinkedList(int v)
    {
        this.data = v;
    }

    //public void add(int i)
    //{
    //    this.next = new MyLinkedList(i);
    //    this.next.next = null;
    //}

    public void printLL()
    {
        MyLinkedList mmm = this;
        while (mmm != null)
        {
            Console.Write(mmm.data);
            Console.Write("->");
            mmm = mmm.next;
        }
    }
}

public static void deleteOdd(ref MyLinkedList mll)
{
    MyLinkedList head, previous, curr;
    head = mll;
    while (head.data % 2 != 0)
    {
        head = head.next;
    }
    mll = head;

    previous = head;
    curr = previous.next;

    while (curr != null)
    {
        if (curr.data % 2 != 0)
        {
            previous.next = curr.next;
            curr = previous.next;
        }
        else
        {
            previous = previous.next;
            curr = curr.next;
        }
    }
}

static void Main(string[] args)
    {
        MyLinkedList myll1 = new MyLinkedList(1); MyLinkedList myll2 = new MyLinkedList(3);
        MyLinkedList myll3 = new MyLinkedList(4); MyLinkedList myll4 = new MyLinkedList(4);
        MyLinkedList myll5 = new MyLinkedList(5); MyLinkedList myll6 = new MyLinkedList(6);
        MyLinkedList myll7 = new MyLinkedList(5); MyLinkedList myll8 = new MyLinkedList(6);
        MyLinkedList myll9 = new MyLinkedList(6); MyLinkedList myll10 = new MyLinkedList(9);
        MyLinkedList myll11 = new MyLinkedList(11); MyLinkedList myll12 = new MyLinkedList(12);

        myll1.next = myll2; myll2.next = myll3; myll3.next = myll4; myll4.next = myll5;
        myll5.next = myll6; myll6.next = myll7; myll7.next = myll8; myll8.next = myll9;
        myll9.next = myll10; myll10.next = myll11; myll11.next = myll12; myll12.next = myll12; myll12.next = null;


    myll1.printLL();
    Console.WriteLine();
    deleteOdd(ref myll1);
    Console.WriteLine();
    myll1.printLL();
}


1326
2
задан 28 января 2018 в 05:01 Источник Поделиться
Комментарии
4 ответа

Отсутствие абстракции

MyLinkedList не очень связный список - это один узел. Отсутствие инкапсуляции список класса делает его трудным для обеспечения повторного использования таких методов, как Add, Remove и Containsи отсутствие такого метода (среди прочих) делает свой связанный список, сложно и чревато ошибками в использовании.


  • MyLinkedList это вводит в заблуждение имя. Что-то вроде MyLinkedListNode было бы более точным.

  • Создание связанного списка класса, который "управляет" его узлов позволяет создавать универсальных методов, как Add и Removeи это можно реализовать IEnumerable и другие полезные интерфейсы (это делает его пригодным для использования с foreach и Linq методы). С такими методами, удаление нечетных записях будет легче. Без них, ваш класс практически бесполезен.

  • Классы коллекций почти всегда универсальные - это делает их пригодными для использования с различными типами данных.

  • printLL не только галстуки классе на консоль (которая VisualMelon уже указывал), но это также не должны быть частью класса (это открытые данные), и это не должно быть частью класса, так как это не способствует основных функций (хранение данных).

  • Все данные в вашем классе является публичной. Это часто плохая идея, поскольку она позволяет код, модифицировать его, и действительно, можно легко создать проблемную государство: a.next = b; b.next = a; (попробуйте позвонить a.printLL() или removeOdd(ref a); на что).

Если вы изобретать колесо для образовательных целей, то не забудьте изучить существующие диски (например LinkedList<T>).

Другие ноты


  • Использование ref вот Хак. Рассмотрим следующую ситуацию: MyLinkedList b = a; deleteOdd(ref b); a.printLL(); - a может все еще содержать нечетные значения. Вам не нужно это, если создать соответствующие связанного класса список.

  • Давя несколько инструкций на одной строке делает код труднее читать. Он также не решает основную проблему, которая заключается в том, что этот связанный список является громоздкой в использовании. Было бы легче, если бы он предложил конструктор, который принимает IEnumerable<T>. И если он был Add способ можно использовать инициализатор коллекции синтаксис: var myList = new MyLinkedList { 1, 3, 5 };.

4
ответ дан 29 января 2018 в 11:01 Источник Поделиться

Простой Комментарий


  • В MSDN предоставляет некоторые соглашения об именовании, соответствующих бита, что public члены должны быть ProperCamelCase (например, Dataне data).

  • Представители общественности, и типы, В идеале должны обладать хотя бы минимальными эксплуатационной документации (\\\), чтобы сделать его совершенно ясно, как использовать API.

  • Это, как правило, лучше вырезать старый код (с комментариями). Он имеет привычку не сохраняется и становится не совместима с Кодексом, что есть. Он также добавляет беспорядка.

  • Для 'экспорта' код, это редко полезно иметь методы, которые явно написать в консоли: гораздо полезнее есть то, что пишет реферат TextWriter (который может занять Console.Out или StreamReader), или что просто возвращает строку. Это дает потребителю больше возможностей.

  • deleteOdd(ref MyLinkedList) вероятно, не может справиться с пустыми списками (передаются им или их возвращения).

  • printLL не лучшее имя переменной: что такое "ЛЛ"? Это член MyLinkedListтак, в "ЛЛ" немного избыточна; я ОФЭКТ некоторое время пытаюсь выяснить, если это как-то связано с печатью слева направо или что-то.

  • mmm не лучшее имя переменной либо: я могу только предположить, что это предназначается, чтобы быть mll!


Альтернативная реализация

Ниже приведены некоторые методы, которые просто вяжутся с твоими, но используя LinkedList<T>и включив некоторые из предложений выше.

Я не знаю, если у вас есть особая причина для нуждающихся в пользовательскую реализацию LinkedList не (не предложенный код), но вы можете реализовать ваши методы с аккуратно .Чистая, построенный в LinkedList<T>, что можно утверждать, чтобы обеспечить более хороший интерфейс API. Важно отметить, что оборачивает связанный список LinkedListNode<T>С под LinkedList<T>, что позволяет некоторым (иллюзия) разделение интересов и избавляет вас от необходимости отслеживать главе списка явно. Она также позволяет вам иметь "пустой" список, это хорошо.

Удалить Нечетные

Этот метод значительно короче, чем раньше, и не требует ref параметр. Это работает с пустыми списками. Это гораздо более понятной реализации, и намного сложнее 'так', потому что API для LinkedList<T>.

/// <summary>
/// Removes odd elements from a LinkedList of integers
/// </summary>
public static void DeleteOdd(LinkedList<int> ll)
{
LinkedListNode<int> cur = ll.First; // grab first node

while (cur != null)
{
var next = cur.Next; // make a note of the next node (will be null if cur is the last element)

if (cur.Value % 2 != 0)
{
ll.Remove(cur); // remove the current node if odd
}

cur = next; // advance to the next node
}
}

printLL

Вот две возможные альтернативы, которые не зависят явным образом Console: один просто создает строку, другой печатает на TextWriter (к сожалению, нет лучшего интерфейса). Это и расширение методов LinkedList<T>но нет особой необходимости.

/// <summary>
/// Renders a linked list as a string
/// </summary>
public static string Render<T>(this LinkedList<T> ll)
{
StringBuilder sb = new StringBuilder();

foreach (var e in ll)
{
sb.Append(e.ToString());
sb.Append("->");
}

return sb.ToString();
}

/// <summary>
/// Prints a linked list to a TextWriter, optionally appending a NewLine
/// </summary>
public static void Print<T>(this LinkedList<T> ll, TextWriter textWriter, bool newLine = true)
{
foreach (var e in ll)
{
textWriter.Write(e.ToString());
textWriter.Write("->");
}

if (newLine)
textWriter.WriteLine();
}

Я не оправдываю наличие newLine параметр не является обязательным, или действительно есть у всех: это просто для иллюстрации некоторых вариантов. Наверное, было бы лучше иметь оба Print и PrintLine если вам нужны оба.

Пример использования

Примечание приятнее API для построения LinkedList<T>.

private static void ExampleUsage()
{
LinkedList<int> ll = new LinkedList<int>();
ll.AddLast(1);
ll.AddLast(2);
ll.AddLast(3);
ll.AddLast(4);
ll.AddLast(5);

Console.WriteLine(ll.Render());
ll.Print(Console.Out);
DeleteOdd(ll);
Console.WriteLine(ll.Render());
ll.Print(Console.Out);
}

4
ответ дан 28 января 2018 в 11:01 Источник Поделиться

Именование переменных:


  • Рассмотрим читатель, который никогда не видел ваш код (который предположительно будет позиция у вас будет в том случае, если вы должны пересмотреть этот код в каких-то 6 месяцев). Что об этих именах: public MyLinkedList(int v) (Что такое в?) и MyLinkedList mmm = this; что mmm? И снова вы назвали int переменной data. Что такое данные?

  • И моя любимая мозоль MyLinkedList myll1 - теперь заключается в том, что 'L' или 'я' капитализируются или это цифра '1'? Это очень трудно сказать, и я бы не советовал делать это.

  • Во-вторых, название “класса LinkedList” имеет определенные коннотации. Это по сути производная класс связанного списка? Я просто говорю, что называние класса есть значительная двусмысленность, и что является врагом писать ясный код. Если кто-то получает экземпляр связанного списка, они вправе ожидать, что они могут вызвать AddFirst способ на нем без проблем? Лучшее название было бы уместно, чтобы отразить это.

  • PrintLL изменение Print? список имеет определенные коннотации. Я, вероятно, хотите, чтобы держаться подальше от списка слово.

(Я вернусь и добавить в дальнейшем suggestiosn для улучшения, когда я получаю возможность - и, при необходимости покажут тесты.).

1
ответ дан 29 января 2018 в 09:01 Источник Поделиться

Имея быстрый взгляд на исходный код, это предполагает, что вы пытаетесь реализовать однонаправленного списка. Это правильно? Исходя из этого я не согласен с предложениями в предыдущих постах использовать LinkedList<T>. Причина в том, что LinkedList<T> реализует двусвязный список, как можно прочитать в описании или в текущем .Объем внедрения. Так что если вы действительно ищете для одного связанного списка, LinkedList<T> не будет работать для вас. Пожалуйста, не поймите меня неправильно, если вы также можете использовать двусвязный список, а затем пойти на это и использовать LinkedList в коллекции, но важно быть осведомлены о различиях между односвязанный список и двусвязный список.

Основываясь на том, что я вижу в приведенном выше исходном коде, я рекомендую следующие доработки:


  • Ваш "MyLinkedList" класс-это фактически "узел" в связанном списке, и должны быть названы так. Пожалуйста, попробуйте также использовать Соглашения об именовании, как они делают свой исходный код гораздо более читабельным.

  • Я рекомендую следующие "способ deleteOdd":

    ListNode current = head;

    while (current != null)
    {

    if (current.data % 2 != 0)
    {
    if(current.previous != null) // As the list is non circular, if current!=head
    {
    current.previous.next = current.next;
    }
    else
    {
    setListHead(current.next); // current is your head
    }
    }

    current = current.next;
    }


    • Попробуйте сделать ваше приложение работает нормально запускать и использовать их для ваших тестовых данных. Лучший способ настроить тестовые предпосылки, конечно, с помощью модульных тестов.


1
ответ дан 29 января 2018 в 11:01 Источник Поделиться