How to remove duplicates from a singly linked list without using a buffer - 2 approaches. | C# Online Compiler

How to remove duplicates from a singly linked list without using a buffer - 2 approaches. by Sandeep Kolte

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using SLL;

public class Program
{
	public static void Main()
	{
		List list = new List();
		// Add a few elements to the list.
		list.Add(5);
		list.Add(5);
		list.Add(8);
		list.Add(5);
		list.Add(1);
		list.Add(1);
		list.Add(0);
		list.Add(9);
		list.Add(7);
		list.Add(21);
		list.Add(7);
		list.Add(0);
		list.Add(8);
		Console.WriteLine();
		Console.WriteLine("Original List:");
		list.ShowNodes();
		Console.WriteLine();
		Console.WriteLine("Removing duplicates...");
		list.RemoveDuplicatesApproach1();
		//list.RemoveDuplicatesApproach2(); // This is another approach to solve the same problem.
		Console.WriteLine();
		Console.WriteLine("List without duplicate nodes:");
		list.ShowNodes();
		// This ensures the command window is displayed in case the program is not run from command prompt.
		Console.ReadLine();
	}
}

namespace SLL
{
	/// <summary>
							    /// A singly linked list class that implements a method to remove duplicate nodes from an unsorted list without using a buffer.
								/// </summary> 
	internal class List
	{
		/// <summary>
														        /// Node class
														        /// </summary>
		internal class Node
		{
			private int data;
			private Node next = null;
			/// <summary>
																					            /// Pointer to next node.
																					            /// </summary>
			internal Node Next
			{
				get
				{
					return next;
				}

				set
				{
					next = value;
				}
			}

			/// <summary>
																					            /// Data stored in the node.
																					            /// </summary>
			internal int Data
			{
				get
				{
					return data;
				}

				set
				{
					data = value;
				}
			}

			/// <summary>
																					            /// Constructor
																					            /// </summary>
																					            /// <param name = "d"></param>
			internal Node(int d)
			{
				data = d;
			}
		}

		private int _length;
		private Node _head;
		/// <summary>
														        /// Length of the list
														        /// </summary>
		internal int Length
		{
			get
			{
				return _length;
			}
		}

		/// <summary>
														        /// Default Constructor
														        /// </summary>
		internal List()
		{
			_length = 0;
			_head = null;
		}

		/// <summary>
														        /// Display all nodes.
														        /// </summary>
		internal void ShowNodes()
		{
			// Print all nodes till the end of the list.
			Node current = _head;
			if (current == null)
			{
				Console.WriteLine("No more nodes to display.");
				Console.WriteLine();
			}
			else
			{
				ShowLength();
				while (current != null)
				{
					Console.WriteLine("Node : " + current.Data);
					current = current.Next;
				}

				Console.WriteLine();
			}
		}

		/// <summary>
														        /// Show length of the list.
														        /// </summary>
		internal void ShowLength()
		{
			string numString = "numbers";
			if (_length == 1)
			{
				numString = "number";
			}

			Console.WriteLine(String.Format("List has [{0}] {1}.", _length.ToString(), numString));
		}

		/// <summary>
														        /// To insert a new Node at the end of the list.
														        /// </summary>
														        /// <param name = "d"></param>
		internal void Add(int d)
		{
			// Create a new Node instance with given data;
			Node newNode = new Node(d);
			Node current = _head;
			if (_head == null)
			{
				_head = newNode;
			}
			else
			{
				// Traverse till the end of the list....
				while (current.Next != null)
				{
					current = current.Next;
				}

				// Add new node as the next node to the last node.
				current.Next = newNode;
			}

			_length++;
		}

		/// <summary>
														        /// Remove duplicates by using two pointers, one running ahead of the other ensuring there are no duplicates.
																/// </summary>
		internal void RemoveDuplicatesApproach1()
		{
			if (_head != null)
			{
				Node a = _head;
				while (a != null)
				{
					Node b = a.Next;
					while (b != null)
					{
						if (a.Data == b.Data)
						{
							a.Next = b.Next;
						}
						else
						{
							if (b.Next != null && a.Data == b.Next.Data)
							{
								b.Next = b.Next.Next;
							}
						}

						b = b.Next;
					}

					a = a.Next;
				}
			}
		}

		/// <summary>
														        /// Another way to remove duplicates by using two pointers, one running ahead of the other ensuring there are no duplicates.
																/// </summary>
		internal void RemoveDuplicatesApproach2()
		{
			if (_head != null)
			{
				Node a = _head;
				while (a != null)
				{
					Node b = a;
					while (b.Next != null)
					{
						if (a.Data == b.Next.Data)
						{
							b.Next = b.Next.Next;
						}
						else
						{
							b = b.Next;
						}
					}

					a = a.Next;
				}
			}
		}

		/// <summary>
														        /// Find node matching the specified number.
														        /// </summary>
														        /// <param name = "d"></param>
														        /// <returns>Returns bool if node matching specifying int is found.</returns>
		internal bool Find(int d)
		{
			bool result = false;
			Node current = _head;
			if (current != null)
			{
				int counter = 1;
				while (current.Next != null && current.Data != d)
				{
					current = current.Next;
					counter++;
				}

				if (current.Data == d)
				{
					result = true;
				}
			}

			return result;
		}
	}
}

​x
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using SLL;
​
public class Program
{
    public static void Main()
    {
        List list = new List();
        // Add a few elements to the list.
        list.Add(5);
        list.Add(5);
        list.Add(8);
        list.Add(5);
        list.Add(1);
        list.Add(1);
        list.Add(0);
        list.Add(9);
        list.Add(7);
        list.Add(21);
        list.Add(7);
        list.Add(0);
        list.Add(8);
        Console.WriteLine();
        Console.WriteLine("Original List:");
        list.ShowNodes();
        Console.WriteLine();
        Console.WriteLine("Removing duplicates...");
        list.RemoveDuplicatesApproach1();
        //list.RemoveDuplicatesApproach2(); // This is another approach to solve the same problem.
        Console.WriteLine();
        Console.WriteLine("List without duplicate nodes:");
        list.ShowNodes();
        // This ensures the command window is displayed in case the program is not run from command prompt.
        Console.ReadLine();
    }
}
​
namespace SLL
{
    /// <summary>
                                /// A singly linked list class that implements a method to remove duplicate nodes from an unsorted list without using a buffer.
                                /// </summary> 
    internal class List
    {
        /// <summary>
                                                                /// Node class
                                                                /// </summary>
        internal class Node
        {
            private int data;
            private Node next = null;
            /// <summary>
                                                                                                /// Pointer to next node.
                                                                                                /// </summary>
            internal Node Next
            {
                get
                {
                    return next;
                }
​
                set
                {
                    next = value;
                }
            }
​
            /// <summary>
                                                                                                /// Data stored in the node.
                                                                                                /// </summary>
            internal int Data
            {
                get
                {
                    return data;
                }
​
                set
                {
                    data = value;
                }
            }
​
            /// <summary>
                                                                                                /// Constructor
                                                                                                /// </summary>
                                                                                                /// <param name = "d"></param>
            internal Node(int d)
            {
                data = d;
            }
        }
​
        private int _length;
        private Node _head;
        /// <summary>
                                                                /// Length of the list
                                                                /// </summary>
        internal int Length
        {
            get
            {
                return _length;
            }
        }
​
        /// <summary>
                                                                /// Default Constructor
                                                                /// </summary>
        internal List()
        {
            _length = 0;
            _head = null;
        }
​
        /// <summary>
                                                                /// Display all nodes.
                                                                /// </summary>
        internal void ShowNodes()
        {
            // Print all nodes till the end of the list.
            Node current = _head;
            if (current == null)
            {
                Console.WriteLine("No more nodes to display.");
                Console.WriteLine();
            }
            else
            {
                ShowLength();
                while (current != null)
                {
                    Console.WriteLine("Node : " + current.Data);
                    current = current.Next;
                }
​
                Console.WriteLine();
            }
        }
​
        /// <summary>
                                                                /// Show length of the list.
                                                                /// </summary>
        internal void ShowLength()
        {
            string numString = "numbers";
            if (_length == 1)
            {
                numString = "number";
            }
​
            Console.WriteLine(String.Format("List has [{0}] {1}.", _length.ToString(), numString));
        }
​
        /// <summary>
                                                                /// To insert a new Node at the end of the list.
                                                                /// </summary>
                                                                /// <param name = "d"></param>
        internal void Add(int d)
        {
            // Create a new Node instance with given data;
            Node newNode = new Node(d);
            Node current = _head;
            if (_head == null)
            {
                _head = newNode;
            }
            else
            {
                // Traverse till the end of the list....
                while (current.Next != null)
                {
                    current = current.Next;
                }
​
                // Add new node as the next node to the last node.
                current.Next = newNode;
            }
​
            _length++;
        }
​
        /// <summary>
                                                                /// Remove duplicates by using two pointers, one running ahead of the other ensuring there are no duplicates.
                                                                /// </summary>
        internal void RemoveDuplicatesApproach1()
        {
            if (_head != null)
            {
                Node a = _head;
                while (a != null)
                {
                    Node b = a.Next;
                    while (b != null)
                    {
                        if (a.Data == b.Data)
                        {
                            a.Next = b.Next;
                        }
                        else
                        {
                            if (b.Next != null && a.Data == b.Next.Data)
                            {
                                b.Next = b.Next.Next;
                            }
                        }
​
                        b = b.Next;
                    }
​
                    a = a.Next;
                }
            }
        }
​
        /// <summary>
                                                                /// Another way to remove duplicates by using two pointers, one running ahead of the other ensuring there are no duplicates.
                                                                /// </summary>
        internal void RemoveDuplicatesApproach2()
        {
            if (_head != null)
            {
                Node a = _head;
                while (a != null)
                {
                    Node b = a;
                    while (b.Next != null)
                    {
                        if (a.Data == b.Next.Data)
                        {
                            b.Next = b.Next.Next;
                        }
                        else
                        {
                            b = b.Next;
                        }
                    }
​
                    a = a.Next;
                }
            }
        }
​
        /// <summary>
                                                                /// Find node matching the specified number.
                                                                /// </summary>
                                                                /// <param name = "d"></param>
                                                                /// <returns>Returns bool if node matching specifying int is found.</returns>
        internal bool Find(int d)
        {
            bool result = false;
            Node current = _head;
            if (current != null)
            {
                int counter = 1;
                while (current.Next != null && current.Data != d)
                {
                    current = current.Next;
                    counter++;
                }
​
                if (current.Data == d)
                {
                    result = true;
                }
            }
​
            return result;
        }
    }
}

Old Message 1
Old Message 2
Old Message 3
New Message
New Message
New Message

Last Run:	8:52:31 pm
Compile:	0.01s
Execute:	0.05s
Memory:	735.69kb
CPU:	0.06s

View IL Code