Implementing Linked Lists in C#
Posted
by nijhawan.saurabh
on ASP.net Weblogs
See other posts from ASP.net Weblogs
or by nijhawan.saurabh
Published on Sat, 06 Oct 2012 18:28:00 GMT
Indexed on
2012/10/07
9:38 UTC
Read the original article
Hit count: 455
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.
© ASP.net Weblogs or respective owner
