Showing posts with label Data Structures and Algorithms. Show all posts
Showing posts with label Data Structures and Algorithms. Show all posts

Part 7- LinkedList Class creation in C# | Linked List Tutorials in C#

 

using System;

using System.Collections.Generic;

using System.Text;


namespace LinkedListTutorial

{

    class LinkedList

    {

        private Node head;

        private int _linkedListSize;


        public LinkedList()

        {

            this.head = null;

            this._linkedListSize = 0;

        }


        public bool IsEmpty 

        {

            get { return this._linkedListSize == 0; }

        

        }


        public int LinkedListSize 

        {

            get { return this._linkedListSize; }

        }

    }

}




Part 6- Implement the Node in Linked List C# | Linked List Tutorials in C#

Node Implementation program in C#

using System;
using System.Collections.Generic;
using System.Text;

namespace LinkedListTutorial
{
   public class Node
    {
        private object data;
        private Node _next;

        public Node(object data, Node next)
        {
            this.data = data;
            this._next = next;
        }

        public object Data
        {
            get { return this.data; }
            
            set { this.data = value; }
        }


        public Node Next
        {
            get { return this._next; }

            set { this._next = value; }
        }
    }
}






Part 4- Type Of Linked List | Linked List Tutorials in C#


Types of Linked List

The types of linked list are mentioned below:

Singly Linked List: Item traversed only in forward direction.

Doubly Linked List: Item traversed in forward and backward directions.

Circular Singly Linked List: Last element contains link to the first element as next.

Singly Linked List:

Singly linked lists contain nodes which have a data part as well as an address part(pointer) i.e. next, which points to the next node in the sequence of nodes.

The operations we can perform on singly linked lists are insertion, deletion and traversal.


Doubly Linked List:

In a doubly linked list, each node contains a data part and two addresses, one for the previous node and one for the next node.


Circular Singly Linked List :

In circular linked list the last node of the list holds the address of the first node hence forming a circular chain.














Part 3- Why we need pointers in Linked List | Linked List Tutorials in C#

 

In case of array, memory is allocated in contiguous manner, hence array elements get stored in consecutive memory locations. So when you have to access any array element, all we have to do is use the array index, for example arr[2] will directly access the 3rd memory location, returning the data stored there.

But in case of linked list, data elements are allocated memory at runtime, hence the memory location can be anywhere. Therefore to be able to access every node of the linked list, address of every node is stored in the previous node, hence forming a link between every node.


We need this additional pointer because without it, the data stored at random memory locations will be lost. We need to store somewhere all the memory locations where elements are getting stored.


Yes, this requires an additional memory space with each node, which means an additional space of O(n) for every n node linked list.