Implementing Linked Lists in C#
- by nijhawan.saurabh
Why?
The question is why you need Linked Lists and why it is the
foundation of any Abstract Data Structure.
Take any of the Data Structures - Stacks, Queues, Heaps,
Trees; there are two ways to go about implementing them -
Using Arrays
Using Linked Lists
Now you use Arrays when you know about the size of the Nodes
in the list at Compile time and Linked Lists are helpful where you are free to
add as many Nodes to the List as required at Runtime.
How?
Now, let's see how we go about implementing a Simple Linked
List in C#.
Note: We'd be dealing with singly
linked list for time being, there's also another version of linked lists - the Doubly
Linked List which maintains two pointers (NEXT and BEFORE).
Class Diagram
Let's see the Class Diagram first:
Code
1 // -----------------------------------------------------------------------
2 // <copyright file="Node.cs" company="">
3 // TODO: Update copyright text.
4 // </copyright>
5 // -----------------------------------------------------------------------
6
7 namespace CSharpAlgorithmsAndDS
8 {
9 using System;
10 using System.Collections.Generic;
11 using System.Linq;
12 using System.Text;
13
14 /// <summary>
15 /// TODO: Update summary.
16 /// </summary>
17 public class Node
18 {
19 public Object data { get; set; }
20
21 public Node Next { get; set; }
22 }
23 }
24
1 // -----------------------------------------------------------------------
2 // <copyright file="LinkedList.cs" company="">
3 // TODO: Update copyright text.
4 // </copyright>
5 // -----------------------------------------------------------------------
6
7 namespace CSharpAlgorithmsAndDS
8 {
9 using System;
10 using System.Collections.Generic;
11 using System.Linq;
12 using System.Text;
13
14 /// <summary>
15 /// TODO: Update summary.
16 /// </summary>
17 public class LinkedList
18 {
19 private Node Head;
20
21 public void AddNode(Node n)
22 {
23 n.Next = this.Head;
24 this.Head = n;
25
26 }
27
28 public void printNodes()
29 {
30
31 while (Head!=null)
32 {
33 Console.WriteLine(Head.data);
34 Head = Head.Next;
35
36 }
37
38 }
39 }
40 }
41
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5
6 namespace CSharpAlgorithmsAndDS
7 {
8 class Program
9 {
10 static void Main(string[] args)
11 {
12 LinkedList ll = new LinkedList();
13 Node A = new Node();
14 A.data = "A";
15
16 Node B = new Node();
17 B.data = "B";
18
19 Node C = new Node();
20 C.data = "C";
21 ll.AddNode(A);
22 ll.AddNode(B);
23 ll.AddNode(C);
24
25 ll.printNodes();
26 }
27 }
28 }
29
Final Words
This is just a start, I will add more posts on Linked
List covering more operations like Delete etc. and will also explore Doubly
Linked List / Implementing Stacks/ Heaps/ Trees / Queues and what not using
Linked Lists.
Normal
0
false
false
false
EN-US
X-NONE
X-NONE
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:"Table Normal";
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-priority:99;
mso-style-parent:"";
mso-padding-alt:0in 5.4pt 0in 5.4pt;
mso-para-margin-top:0in;
mso-para-margin-right:0in;
mso-para-margin-bottom:10.0pt;
mso-para-margin-left:0in;
line-height:115%;
mso-pagination:widow-orphan;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:"Times New Roman";
mso-bidi-theme-font:minor-bidi;}