how to create intersecting linked lists in C#?

Question

Hi,

I'm trying to create 2 linked list with a common intersection node. As I see this is a very hot question in LinkedList to find the intersection node. I have written following code but it throws InvalidOperationexception.

        LinkedList<int> LL = new LinkedList<int>();
        LL.AddFirst(5);
        LL.AddFirst(4);
        LL.AddFirst(3);
        LL.AddFirst(2);
        LL.AddFirst(1);

        LinkedListNode<int> sectionNode = LL.Find(3);
        LinkedList<int> LL2 = new LinkedList<int>();
        LL2.AddFirst(100);
        LL2.AddFirst(90);
        LL2.AddFirst(80);
        LL2.AddFirst(sectionNode);

Could someone please guide me how I can create a Y shaped linked list in C#.

Answer 1

It's not supported. The node keeps track of its List, which you can access through a get-only property. That means a node can't be in two lists at once, and you can only change the parent list by removing then adding.

This is clearly designed to protect people from mistakes, but it also makes what you want impossible. Note that LinkedList is doubly linked, so you if this worked, you would have to arbitrarily pick both the List and the Previous reference.

You can use (or write) a third-party implementation with different behavior. For example, this code implements a singly-linked list. Nodes don't have references to their containing list, so a Y should be fine.