Создание пользовательского LinkedList

Question

Я работаю над созданием собственного LinkedList. Но я не могу решить эту ошибку. Может кто-нибудь мне помочь!

Проблема в том, что я хочу вставить объект после определенного элемента. Я создал метод Find для поиска этого конкретного элемента и возврата его ссылки, но я не могу его решить.

CustomLinkedList c = new CustomLinkedList(); 
     c.Add(31); 

     c.Add(45); 

     c.Add(23); 

     c.Add(36); 

     c.PrintList(); 

     Console.WriteLine("\n" + " Process of adding item at a spectifed location"); 
     c.Addafter(66,23); 


     c.PrintList(); 

class Node 
{ 

    public object Element; 
    public Node Link; 

    public Node() 
    { 
     Element = null; 
     Link = null; 
    } 

    public Node(object TheElement) 
    { 
     Element = TheElement; 
     Link = null; 
    } 

class CustomLinkedList 
{ 
    protected Node header; 
    protected Node last; 

    public CustomLinkedList() 
    { 
     //header = new Node("header"); 
    } 

    private Node Find(object Item) 
    { 
     Node Current = new Node(); 
     Current = header; 
     while (Current.Element != Item && Current.Link !=null) 
     { 
      Current = Current.Link; 
     } 
     return Current; 
    } 


    public void PrintList() 
    {    
     Node n = new Node(); 
     n = header; 
     while (n != null) 
     { 
      Console.WriteLine(n.Element); 
      n = n.Link; 
     } 
    } 

    public void Add(object a) 
    { 
     Node n = new Node(); 
     n.Element = a; 
     n.Link = null; 
     if (last == null) 
     { 
      header = n; 
      last = n; 
     } 
     else 
     { 
      last.Link = n; 
      last = n; 
     } 
    } 

    public void Addafter(object newitem, object After) 
    { 
     Node current = new Node(); 
     Node newNode = new Node(newitem); 
     current = Find(After); 

     newNode.Link = current.Link; 
     current.Link = newNode; 
    } 
} 

Answer 1

Ваш код имеет 2 проблемы

• Find() функция возвращает элемент Tail, когда элемент не в списке.
• Сравнение n.Element и Item сложно, если они имеют тип object. Сделайте свои классы обобщенными, чтобы решить это.

...

class CustomLinkedList<T> where T : IEquatable 
    { 
    .... 

    private Node Find(object Item) 
    { 
     Node Current = header; // null for empty list 

     //while (Current.Element != Item && Current.Link !=null) 
     while(Current != null) 
     { 
      if (Current.Equals(Item)) // can't always use == 
       break; 
      Current = Current.Link; 
     } 
     return Current; 
    } 
} 

Answer 2

Я не знаю, что вы используете для тестирования, но стоимость типов не будет работать так, как вы думаете, это должно, потому что значения коробки сравниваются.

Например, это всегда будет возвращать 3 (последний элемент в списке)

CustomLinkedList cList= new CustomLinkedList(); 
cList.Add(1); 
cList.Add(2); 
cList.Add(3); 

Console.WriteLine(cList.Find(2).Element); 

, но это будет работать (выход 2)

CustomLinkedList cll = new CustomLinkedList(); 
object a = 1; 
object b = 2; 
object c = 3; 
cll.Add(a); 
cll.Add(b); 
cll.Add(c); 

Console.WriteLine(cll.Find(b).Element); 

То же самое идет для ссылочных типов, которые не реализуют операторы! =. Так строки будут работать, но мало еще будет

Answer 3

Причины, почему он не работает на этой линии:

while (Current.Element != Item && Current.Link !=null) 

== The и != операторов для проверки object типа для равенства ссылок. Если вы используете свой список со значением типа (например, int), значения будут помещаться в отдельные объекты, а оператор != всегда будет возвращать true (см. this article для получения подробной информации о боксе).

Рассмотрим это:

object x = 42; 
object y = 42; 
Console.WriteLine(x == y); // prints False 
Console.WriteLine(x.Equals(y)); // prints True 

Ваш текущий код работает отлично с ссылочных типов:

var list = new CustomLinkedList(); 
list.Add("hello"); 
list.Add("!"); 
list.Addafter("world", "hello"); 
list.PrintList(); 

Выход:

привет
мир
!

Но для типов значений она не находит "после" значения, поэтому он добавляет новый элемент в конец списка:

var list = new CustomLinkedList(); 
list.Add(1); 
list.Add(3); 
list.Addafter(2, 1); 
list.PrintList(); 

Выход:

Так y НУ нужно заменить оператор == с вызовом Equals:

while (!object.Equals(Current.Element, Item) && Current.Link !=null)