Hello! How can I write a method that would remove the elements of a doubly linked list that are in odd positions. The class method interests.

I wrote a certain solution: I created a new list, added elements that are in even positions; cleared the list for which the method was called; elements from the new list are added to the same list.

public void RemoveAtOddPosition() { LinkedList<T> newList = new LinkedList<T>(); for (int i = 0; i < Count(); i++) { if (i % 2 == 0) { newList.Add(this[i]); } } Clear(); for (int i = 0; i < newList.Count(); i++) { Add(newList[i]); } }

But can there be any correct solution using links to the previous and next elements?

Class node

 public class Node<T> { public T Data { get; set; } public Node<T> Previous { get; set; } public Node<T> Next { get; set; } public Node(T data) { Data = data; } }

LinkedList class

 public class LinkedList<T> { Node<T> head; Node<T> tail; int count; public bool IsEmpty() { return count == 0; } public int Count() { return count; } public T this[int index] { get { if (index < 0) throw new ArgumentOutOfRangeException(); Node<T> current = head; for (int i = 0; i < index; i++) { if (current.Next == null) throw new ArgumentOutOfRangeException(); current = current.Next; } return current.Data; } } public void Show() { Console.WriteLine("Двунаправленный список"); Node<T> tmp = head; while (tmp != null) { Console.Write(tmp.Data + " "); tmp = tmp.Next; } Console.WriteLine(); } public void Clear() { head = tail = null; count = 0; } public void Add(T data) { Node<T> node = new Node<T>(data); if (head == null) { head = node; } else { tail.Next = node; node.Previous = tail; } tail = node; count++; } public void RemoveAtOddPosition() { LinkedList<T> newList = new LinkedList<T>(); for (int i = 0; i < Count(); i++) { if (i % 2 == 0) { newList.Add(this[i]); } } Clear(); for (int i = 0; i < newList.Count(); i++) { Add(newList[i]); } } }
  • 2
    "maybe there is any right decision" - of course there is. This is done in a single pass, by linking Previous/Next elements in even positions, without constantly obtaining elements by index, which in this case is an expensive operation. - Igor
  • then how do i get access to the elements? leave the cycle, leave the condition, and then what? It’s not possible to get Previous / Next elements through an iterator. - Dmitry Bystrov
  • Is the LinkedList<T> class yours? - Igor
  • if in terms of writing - mine. And so the implementation is spied on some sources - Dmitry Bystrov
  • So you can bring the Head and Tail properties out from LinkedList<T> ? - Igor

1 answer 1

This is done in a single pass, by linking Previous / Next elements in even positions, without constantly obtaining elements by index, which in this case is an expensive operation.

 public void RemoveAtOddPosition() { int index = 0; Node<T> current = head; // at position 0, leave it in list while (current != null && current.Next != null) { // we come here knowing, that current was at even position: // need to remove current.Next current = current.Next; // now current is at odd index, take it out: current.Previous.Next = current.Next; if (current.Next != null) current.Next.Previous = current.Previous; // put current to next even index: current = current.Next; } // TODO: recalculate count and tail - left as an exercise for the reader // this can also be done inside while loop above tail = null; count = 0; current = head; while (current != null) { count++; if (current.Next == null) tail = current; current = current.Next; } }
  • I figured out the recalculation of the elements in the list: I added count-- to the body of the loop with the last line. But with the tail element is a bit unclear. Suppose there is a sequence 1,2,3,4,5,6,7,8,9,10 , in which tail is 10 When you remove elements at odd places, there are elements 1,3,5,7,9 . It turns out that the tail element was also removed. Probably need to do tail = current.Next every time inside the loop? - Dmitry Bystrov
  • @ BystrovDmitry added in the response code - Igor