Archive for the ‘ LinkList ’ Category

Write A Program To Reverse a Doubly Linked List

Today we have to write a program for reversing a Doubly linked list. A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes’ previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.

image

Source : http://en.wikipedia.org/wiki/Doubly-linked_list

Code

        public DoubleNode<T> Reverse()
        {
            DoubleNode<T> newHead = null;
            while (head != null)
            {
                DoubleNode<T> temp = head;
                head = head.Next;
                temp.Next = newHead;
                newHead = temp;
            }
            return newHead;
        }

Write a Program for Swapping Every Second Element of LinkList

Input : 0->1->2->3->4->5->6->7->8->9->

output: 1->0->3->2->5->4->7->6->9->8->

Code :

        public void SwapEverySecondElement()
        {
            var p = head;
            var q = p.Next;

            while (q != null)
            {
                var temp = p.Data;
                p.Data = q.Data;
                q.Data = temp;
                p = q.Next;
                if (p != null)
                {
                    q = p.Next;

                }
                else
                {
                    q = null;
                }

            }

        }

Test

Input

0->1->2->3->4->5->6->7->8->9->

Output

1->0->3->2->5->4->7->6->9->8->

——————————————————————————–

Input

A->B->C->D->E->F->G->H->I->J->K->L->M->N->O->P->Q->R->S->T->U->V->W->X->Y->Z->

Output

B->A->D->C->F->E->H->G->J->I->L->K->N->M->P->O->R->Q->T->S->V->U->X->W->Z->Y->

Write A Program to Detect Loop in Singly LinkedList

Given a single linked list, we have to detect loop. For this we will use two pointers called slow and fast. We will increment slow by one and fast by two. once both these pointers meet, this is the node from were loop is present

        public void DetectLoop(Node<T> node)
        {
            Node<T> slow = node;
            Node<T> fast = node;

            while (slow != fast && fast.Next != null)
            {
                slow = slow.Next;
                fast = fast.Next.Next;
                if (slow == fast)
                {
                    Console.WriteLine("Loop is detected");
                    return;
                }
            }
            Console.WriteLine("There is no loop");

        }

Write a Program to Implement Doubly Link List

A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes’ previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.

image_thumb3

Source : http://en.wikipedia.org/wiki/Doubly-linked_list

Code

    public class DoubleLinkList<T>
    {
        private DoubleNode<T> head;
        private DoubleNode<T> tail;

        public int InsertAtHead(DoubleNode<T> item)
        {

            if (head == null)
            {
                item.Next = item.Previous = null;
                head = item;
                tail = item;
                return 0;
            }

            head.Previous = item;
            item.Next = head;
            head = item;

            return 0;
        }
        
        public int InsertAtTail(DoubleNode<T> item)
        {
            if (head == null)
            {
                item.Next = item.Previous = null;
                head = item;
                tail = item;
                return 0;
            }

            tail.Next = item;
            item.Previous = tail;
            tail = item;
            return 0;
        }

        public void ShowFromHead()
        {
            var temp = head;
            while (temp != null)
            {
                Console.Write(temp.Data + "->");
                temp = temp.Next;
            }
            Console.WriteLine(Environment.NewLine);
        }

        public void ShowFromHead(DoubleNode<T> root)
        {
            var temp = root;
            while (temp != null)
            {
                Console.Write(temp.Data + "->");
                temp = temp.Next;
            }
            Console.WriteLine(Environment.NewLine);
        }

        public void ShowFromTail()
        {
            var temp = tail;
            while (temp != null)
            {
                Console.Write(temp.Data + "->");
                temp = temp.Previous;
            }
            Console.WriteLine(Environment.NewLine);
        }
    }

    public class DoubleNode<T>
    {
        public DoubleNode<T> Next { get; set; }
        public DoubleNode<T> Previous { get; set; }
        public T Data { get; set; }

    }

Write a Program to Append last n nodes of a linked list to the beginning of the list

Today we will write a program for appending last N nodes from the beginning to the start of the link list.

Example

input linked is 0->1->2->3->4->5->6->7->8->9 and the value of N is 3 than output must be

7->8->9->0->1->2->3->4->5->6

Code

        public void AppendLastNNodeToHead(Node<T> root, int n)
        {
            Node<T> currentNode = root;
            Node<T> previousNode = root;

            for (int i = 0; i < n; i++)
            {
                currentNode = currentNode.Next;
                if (currentNode == null)
                {
                    Console.WriteLine("List has less number of nodes");
                    return;
                }
            }

            while (currentNode.Next != null)
            {
                currentNode = currentNode.Next;
                previousNode = previousNode.Next;
            }

            currentNode.Next = root;
            root = previousNode.Next;
            previousNode.Next = null;

            this.head = root;
        }

Write a Program to Print Kth Element from Tail in a LinkList

Today we will write a program for finding the Kth  element from the last.

Code

        public void PrintKthElementFromLast(Node<T> head, int k)
        {
            Node<T> firstPointer = head;
            Node<T> secondPointer = head;
            int counter = 0;
            while (counter < k)
            {
                if (firstPointer == null)
                {
                    Console.WriteLine("LinkList has less number of nodes");
                    return;
                }
                firstPointer = firstPointer.Next;
                counter = counter + 1;
            }
            while (firstPointer != null)
            {
                secondPointer = secondPointer.Next;
                firstPointer = firstPointer.Next;
            }
            Console.WriteLine(string.Format("{0}th Elements from Last is {1} ", k, 
secondPointer.Data)); Console.WriteLine(Environment.NewLine); }

Test Case

1->2->3->4->5->6->

2th Elements from Last is 5


1->2->3->4->5->6->20->17->1->7->

3th Elements from Last is 17


1->2->3->4->5->6->20->17->1->7->

4th Elements from Last is 20


1->2->3->4->5->6->20->17->1->7->

10th Elements from Last is 1

Write a Program to Reverse Single List using Iterative Procedure

In the past we have already covered reversing a Linked List via Recursion.  Today we will discuss how we can reverse a Linked List using Iterative method.

Algorithm

  1. Take three pointer currentNode,nextNode and previousNode
  2. initialize currentNode to head of the linked List
  3. iterate over the linked list until currentNode is equal to null
    1. nextNode to previousNode
    2. previousNode to currentNode
    3. In the loop change currentNode to next Node
  4. return previousNode

Code

        public Node<T> ReverseIterative()
        {

            Node<T> currentNode = this.head;
            Node<T> previousNode, nextNode;
            previousNode = nextNode = null;

            while (currentNode != null)
            {
                nextNode = currentNode.Next;
                currentNode.Next = previousNode;
                previousNode = currentNode;
                currentNode = nextNode;

            }
            return previousNode;
        }

Write a Program to Find The count of a Given number in a Single Linked List

Algorithm

  1. Initialize number counter to 0
  2. Loop through the linked list
    1. if current node value is equal to number, increment the counter
  3. return counter

Code

        public int NumberCount(T number)
        {
            int count = 0;
            Node<T> temp = this.head;

            while (temp != null)
            {
                if (temp.Data.Equals(number))
                {
                    count = count + 1;
                }
                temp = temp.Next;
            }
            return count;
        }

sub list of a sorted (ascending order)link list is reversed. correct it

sub list of a sorted (ascending order)link list is reversed. correct it.

Input
1->2->3->4->8->7->6->5->9->10->11
Output
1->2->3->4->5->6->7->8->9->10->11

To solve this problem :

  1. Find the pointer, from dis order starts say first
  2. Find the pointer where dis order ends say last node
  3. Setting next of last node to null
  4. Reverse the linked list from first to last
  5. join the linked list with reversed linked list
  6. join the linked list with remaining list

Node Class : Used for Creating Link List

public class Node<T>
  {
    private T nodeValue;
    private Node<T> nextNode;

    public Node()
    {
      this.nodeValue = default(T);
      this.nextNode = null;
    }

    public Node(T nodeValue)
    {
      this.nodeValue = nodeValue;
      this.nextNode = null;
    }

    /// <summary>
    /// Value of node
    /// </summary>
    public T NodeValue
    {
      get { return nodeValue; }
      set { this.nodeValue = value; }
    }

    /// <summary>
    /// The node this node links to
    /// </summary>
    public Node<T> NextNode
    {
      get { return this.nextNode; }
      set { this.nextNode = value; }
    }
  }
    /// <summary>
    /// 1--->2--->3--->4--->9--->8-->7--->6--->5--->10--->11--->NULL
    /// </summary>
    /// <param name="head"></param>
    public static void correctList(Node<int> head)
    {

      if (head == null)
      {
        Console.WriteLine("Empty List");
        return;
      }

      Node<int> current = head;
      Node<int> first = null;
      Node<int> last = null;
      Node<int> mark1 = null;

      while (current != null && current.NodeValue < current.NextNode.NodeValue)
      {
        mark1 = current;
        current = current.NextNode;
      }

      first = current; //Pointer to node, LL Disorder starts

      while (current != null && current.NodeValue > current.NextNode.NodeValue)
        current = current.NextNode;


      last = current.NextNode; //Pointer to node, LL Disorder Ends

      current.NextNode = null; // Setting next of last node to null

      Reverse(ref first);//reverse the sub list that dis order starts to disorder ends

      mark1.NextNode = first; // join the initial linklist with reversed linkedlist 

      while (first.NextNode != null)
      {
        first = first.NextNode;
      }

      first.NextNode = last; // join the merged link list with sorted linklist
      Console.WriteLine();
      Console.WriteLine("Output");
      
      PrintList(head);
      Console.WriteLine();

    }

    public static void Reverse(ref Node<int> head)
    {

      Node<int> first;
      Node<int> rest;
      if (head == null) return;
      first = head;
      rest = first.NextNode;
      if (rest == null) return;
      Reverse(ref rest);
      first.NextNode.NextNode = first;
      first.NextNode = null;
      head = rest;

    }
    public static void PrintList(Node<int> head)
    {
      while (head != null)
      {
        Console.Write(head.NodeValue);
        head = head.NextNode;
        if (head != null) Console.Write("->");
      }

    }

Main Program

      Node<int> a = new Node<int>(1);
      Node<int> a1 = new Node<int>(2);
      Node<int> a2 = new Node<int>(3);
      Node<int> a3 = new Node<int>(4);
      Node<int> a4 = new Node<int>(8);
      Node<int> a5 = new Node<int>(7);
      Node<int> a6 = new Node<int>(6);
      Node<int> a7 = new Node<int>(5);
      Node<int> a8 = new Node<int>(9);
      Node<int> a9 = new Node<int>(10);
      Node<int> a10 = new Node<int>(11);

      a.NextNode = a1;
      a1.NextNode = a2;
      
      a2.NextNode = a3;
      
      a3.NextNode = a4;
      
      a4.NextNode = a5;
      
      a5.NextNode = a6;
      
      a6.NextNode = a7;
      
      a7.NextNode = a8;
      
      a8.NextNode = a9;

      a9.NextNode = a10;
      
      a10.NextNode = null;
      Console.WriteLine("Input");
      Microsoft.PrintList(a);
      Microsoft.correctList(a);

Reverse LinkList using Recursion

Node Class : For creating LinkList

public class Node<T>
    {
        private T nodeValue;
        private Node<T> nextNode;

        public Node()
        {
            this.nodeValue = default(T);
            this.nextNode = null;
        }

        public Node(T nodeValue)
        {
            this.nodeValue = nodeValue;
            this.nextNode = null;
        }

        /// <summary>
        /// Value of node
        /// </summary>
        public T NodeValue
        {
            get { return nodeValue; }
            set { this.nodeValue = value; }
        }

        /// <summary>
        /// The node this node links to
        /// </summary>
        public Node<T> NextNode
        {
            get { return this.nextNode; }
            set { this.nextNode = value; }
        }
    }

LinkList

class LinkList
    {
        public static void Test()
        {
            // Create a link list
            Node<int> a1 = new Node<int>();
            a1.NodeValue = 10;

            Node<int> a2 = new Node<int>();
            a2.NodeValue = 11;

            Node<int> a5 = new Node<int>();
            a5.NodeValue = 12;

            Node<int> a3 = new Node<int>();
            a3.NodeValue = 13;

            Node<int> a4 = new Node<int>();
            a4.NodeValue = 14;
            a1.NextNode = a2;
            a2.NextNode = a3;
            a3.NextNode = a4;
            a4.NextNode = a5;
            a5.NextNode = null;

            //reverse the link list
            
            Console.WriteLine("----------------------------------------------------");
            Console.WriteLine("Reverse  List");           
            Reverse(ref a1);           
            PrintLinkList(a1);
            Console.WriteLine("----------------------------------------------------");

        }
        public static void Reverse(ref Node<int> head)
        {

            Node<int> first;
            Node<int> rest;
            if (head == null) return;
            first = head;
            rest = first.NextNode;
            if (rest == null) return;
            Reverse(ref rest);
            first.NextNode.NextNode = first;
            first.NextNode = null;
            head = rest;

        }
        public static void PrintLinkList(Node<int> head)
        {
            var temp = head;
            while (temp != null)
            {
                Console.Write(temp.NodeValue + "-->"
                  );
                temp = temp.NextNode;

            }
            Console.WriteLine();

        }




    }