How to properly make a linked list with cursom links?

Question

When creating a LinkedList in C#, you can specify the type of its node via templates LinkedList<T>, but you can't specify the type of its links. It is always LinkedListNode. And this is weird because, mathematically, graph nodes can carry data (weidth of edges etc.). This is not impossible to implement, even, but they chose not to. My question is: how do i represent linked list with custom nodes and links? Do i necessarily have to write my own implementation of linked list?

Answer 1

You could build your own linked list type, but you can also just place the edge-related data into the stored object.

A simple version of that would be:

public class NodeInfo 
{
  public NodeInfo(string data, double prevWeight = 1.0, double nextWeight = 1.0)
  {
    Data = data;
    PrevLinkWeight = prevWeight;
    NextLinkWeight = nextWeight;
  }

  public string Data { get; set; }
  public double PrevLinkWeight { get; set; }
  public double NextLinkWeight { get; set; }
}

You'd then add the nodes like this:

var list = new LinkedList<NodeInfo>();
list.AddLast(new NodeInfo("Node1", nextWeight: 0.5));
list.AddLast(new NodeInfo("Node2", prevWeight: 0.5, nextWeight: 1.0));
list.AddLast(new NodeInfo("Node3", prevWeight: 2.0));

And, given a LinkedListNode<NodeInfo>, you'd access the node/edge data in this way:

node.Value.Data
node.Value.NextLinkWeight

A more involved approach:

You can also do something slightly more complicated - e.g. have separate types for the nodes and for the edges:

// Container class
public class NodeInfo<TValue>
{
  public NodeInfo(
    TValue value, 
    LabeledWeightedLink prevLink = null, 
    LabeledWeightedLink nextLink = null)
  {
    Data = value;
    PrevLink = prevLink ?? new LabeledWeightedLink();
    NextLink = nextLink ?? new LabeledWeightedLink();
  }

  public TValue Data { get; set; }
  public LabeledWeightedLink PrevLink { get; set; }
  public LabeledWeightedLink NextLink { get; set; }
}

// Edge-related data
public class LabeledWeightedLink 
{
  public LabeledWeightedLink()
    : this(string.Empty, 1.0)
  {}

  public LabeledWeightedLink(string label, double weight = 1.0)
  {
    Label = label;
    Weight = weight;
  }
  public string Label {get; set; }
  public double Weight { get; set; }

  public override string ToString() => $"lnk(\"{Label}\"; {Weight})";
}

You could then add nodes like this:

var list = new LinkedList<NodeInfo<string>>(); 

list.AddLast(new NodeInfo<string>(
  "node1",
  nextLink: new LabeledWeightedLink("1 to 2", 2.0)));

list.AddLast(new NodeInfo<string>(
  "node2", 
  prevLink: new LabeledWeightedLink("2 to 1", 1.0),
  nextLink: new LabeledWeightedLink("2 to 3", 2.0)));

list.AddLast(new NodeInfo<string>(
  "node3",
  prevLink: new LabeledWeightedLink("3 to 2", 2.5),
  nextLink: new LabeledWeightedLink("3 to 4", 1.5)));

list.AddLast(new NodeInfo<string>(
  "node4",
  prevLink: new LabeledWeightedLink("4 to 3", 1.5)));

Again, given a node, you'd access various properties of interest by going through the NodeInfo class:

node.Value.Data
node.Value.NextLink.Label
node.Value.NextLink.Weight

For example:

var current = list.First;
do {
  string nodeData = current.Value.Data;
  string prevLink = current.Value.PrevLink.ToString();
  string nextLink = current.Value.NextLink.ToString();
  Console.WriteLine($"{prevLink}<---[{nodeData}]--->{nextLink}");

  current = current.Next;
} while (current != null);

This prints out:

lnk(""; 1)<---[node1]--->lnk("1 to 2"; 2)
lnk("2 to 1"; 1)<---[node2]--->lnk("2 to 3"; 2)
lnk("3 to 2"; 2.5)<---[node3]--->lnk("3 to 4"; 1.5)
lnk("4 to 3"; 1.5)<---[node4]--->lnk(""; 1)

Answer 2

yes you have to write your own. You could use the reference source as a starter https://referencesource.microsoft.com/#System/compmod/system/collections/generic/linkedlist.cs

sounds like a fun project, if you get stuck post questions (with code ) here