Linked List : Find middle element.

Find the middle element of the linked list.

Note: Use linked list created in this blog page: Singly Linked List

Logic:

Here we have two pointers in linked list, slow pointer (slowPointer) and fastpointer (fastPointer), slow pointer steps one node at a time but fast pointer steps 2 nodes at a time. slowPointer and fastPointer pointer keeps on traversing linked list till we reach end of linked list. At the end our slow pointer will be pointing to middle element of the linked list.
  

   public T FindMiddle()

        {

            Node fastPointer = this.Head;

            Node slowPointer = this.Head;

            while (fastPointer.next != null && fastPointer.next.next !=null)

            {

                fastPointer = fastPointer.next.next;

                slowPointer = slowPointer.next;

            }

            return slowPointer.content;

   }

Linked List : Reverse link list iteratively

Note: Use linked list created in this blog page: Singly Linked List

  

  public void Reverse()

       {

            Node current = this.Head;

            Node Next = null;

            Node Prev = null;

            while (current != null)

            {

                Next = current.next;

                current.next = Prev;

                Prev = current;

                current = Next;               

            } 

            this.Head = Prev; 

        }

Linked List: Find nth element from end.

Find nth element from the end of the linked list.

Note: Use linked list created in this blog page: Singly Linked List

Logic:

Here we have two pointers in linked list, root pointer (tempRoot) and nth node pointer (tempNth), tempRoot pointer keeps on traversing linked list till we have a difference of n nodes between Head and tempRoot. Then assign head to tempNth so that we have difference of n nodes between tempRoot and tempNth. Now, keep on traversing linked list, by incrementing both pointers, till we reach end of linked list. At the end our tempNth pointer will be pointing to nth element from end.

   

        public T Find_nth_fromEnd(int pIndex)

        {

            T returnValue = default(T);

            int counter = pIndex;

            // We have pointer to head of linked list.

            Node tempRoot = this.Head;  

            Node tempNth;

            while (counter > 1)

            {

                tempRoot = tempRoot.next;

                if (tempRoot == null)

                {

                    return returnValue;

                }

                counter--;

            }

            tempNth = this.Head;

            while (tempRoot.next != null)

            {

                tempNth = tempNth.next;

                tempRoot = tempRoot.next;

            }

            return tempNth.content;

        }

C#: Doubly Link list

Here is the code to create a doubly link list in C#. 

It supports insert/add, traverse (backward/forward), Contains, Index of and delete operations.

class DoublyListList

{

        //Point to current node (last node).

        Node Current = null;

        // Point to head node.

        Node Head = null;

        // Node class declaration.

        class Node

        {

            public T content;

            public Node next;

            public Node previous;

        }

        ///

        /// Add node as current/last node.

        ///

        /// Node content.

        public void Add(T objconent)

        {

            Console.WriteLine(string.Format("*** Add Value {0}", objconent.ToString()));

            Node objNode = new Node()

            {

                content = objconent

            };

            if (Head == null)

            {

                Head = objNode;

            }

            else

            {

                objNode.previous = Current;

                Current.next = objNode;               

            }

            Current = objNode;

            Console.WriteLine("Content {" + objconent.ToString() + "} added.");

        }

        ///

        /// Add node as current/last node.

        ///

        /// Node content.

        public void AddFirst(T objconent)

        {

            Console.WriteLine(string.Format("*** Add Value {0}", objconent.ToString()));

            Node objNode = new Node()

            {

                content = objconent

            };

            if (Head == null)

            {

                Head = objNode;

            }

            else

            {

                objNode.next = Head;

                Head.previous = objNode;

            }

            Head = objNode;

            Console.WriteLine("Content {" + objconent.ToString() + "} added.");

        }

        ///

        /// Add node as current/last node.

        ///

        /// Node content.

        public void AddLast(T objconent)

        {

            this.Add(objconent);

        }

        ///

        /// List down all elements of linked list in forward manner.

        ///

        private void ListNodesForward()

        {

            Console.WriteLine("*** List nodes in forward manner:");

            Node tempNode = Head;

            while (tempNode != null)

            {

                Console.WriteLine(tempNode.content);

                tempNode = tempNode.next;

            }

        }

        ///

        /// List down all elements of linked list in backward manner.

        ///

        private void ListNodesBackward()

        {

            Console.WriteLine("*** List nodes in backward manner:");

            Node tempNode = Current;

            while (tempNode != null)

            {

                Console.WriteLine(tempNode.content);

                tempNode = tempNode.previous;

            }

        }

        ///

        /// Return index of particular node.

        ///

        /// Node content.

        /// Index of node content.

        public bool Contains(T objconent)

        {

            return this.IndexOf(objconent) > -1 ? true : false;          

        }

        ///

        /// Return index of particular node.

        ///

        /// Node content.

        /// Index of node content.

        public int IndexOf(T objconent)

        {

            Console.WriteLine(string.Format("*** Index of {0}:", objconent.ToString()));

            Node tempNode = Head;

            int Counter = 0;

            while (tempNode != null)

            {

                if (tempNode.content.Equals(objconent))

                {

                    return Counter;

                }

                tempNode = tempNode.next;

                Counter++;

            }

            return -1;

        }

        ///

        /// Delete node.

        ///

        /// Node content.

        public void Delete(T pValue)

        {

            Console.WriteLine(string.Format("*** Delete Value {0}:", pValue.ToString()));

            Node tempNode = Head;

            Node preNode = Head;

            int Counter = 0;

            while (tempNode != null)

            {

                if (tempNode.content.Equals(pValue))

                {

                    preNode.next = tempNode.next;

                    tempNode.next.previous = preNode;

                    return;

                }

                preNode = tempNode;

                tempNode = tempNode.next;

                Counter++;

            }

        }

        public void ListNodes()

        {

            this.ListNodesForward();

            this.ListNodesBackward();

        }

    }