Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Adding a LinkedList to a LinkedList

linked list

  • Please log in to reply
8 replies to this topic

#1 mctim

mctim

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 110 posts

Posted 26 January 2012 - 09:24 AM

Let's say I have 2 linked lists foo and bar and I want to add foo to bar will this work? More specifically will bar's last node pointer be pointing to foo's last node pointer, or will I have to iterate through foo and add each node 1 at a time?
bar.AddLast(foo.First);

  • 0

#2 gregwarner

gregwarner

    Obi Wan of Programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1586 posts
  • Location:Arkansas
  • Programming Language:C, Java, C++, C#, PHP, Transact-SQL

Posted 26 January 2012 - 09:56 AM

I'm assuming you're using the LinkedList in System.Collections.Generic. If this is not the case, please correct me.

bar.AddLast(foo.First);


The above line throws an InvalidOperationException with a message of "The LinkedList node already belongs to a LinkedList."

It doesn't let you arbitrarily add nodes from one list to another. They must be removed from the list and then added to the other list. If you want to add all of foo's elements to bar, you'll need to iterate over foo.

For example:
while (foo.Count > 0) {
    LinkedListNode<[I]Type[/I]> node = foo.First;
    foo.RemoveFirst();
    bar.AddLast(node);
}

(Where Type is the type of LinkedList you declared.)
  • 0

ti-99-sig.png
Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law.
– Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid


#3 mctim

mctim

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 110 posts

Posted 26 January 2012 - 10:03 AM

Any idea why they implemented LinkedList like that? It seems a little odd to me because I would think you could add a whole List in O(1) time if you just moved some pointers, but if you do it like that you'll end up w/ O(n). I guess there is always the "roll your own" option.
  • 0

#4 lespauled

lespauled

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1360 posts
  • Programming Language:C, C++, C#, JavaScript, PL/SQL, Delphi/Object Pascal, Visual Basic .NET, Pascal, Transact-SQL, Bash

Posted 26 January 2012 - 11:10 AM

Actually, I was wondering why you were using a LinkedList<T> and not a standard List<T>. Usually List is usually more efficient, especially in memory allocation. In any case, IEnumerable has a Union extension method.
  • 0

#5 mctim

mctim

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 110 posts

Posted 26 January 2012 - 11:14 AM

Well that's good to know, because my whole reason for using it was so I could add whole lists at a time w/out having to iterate through my list.
  • 0

#6 lespauled

lespauled

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1360 posts
  • Programming Language:C, C++, C#, JavaScript, PL/SQL, Delphi/Object Pascal, Visual Basic .NET, Pascal, Transact-SQL, Bash

Posted 26 January 2012 - 11:26 AM

this would basically do the same as a union.

foo.AddRange(bar.FindAll( x => foo.IndexOf(x.ToString()) == -1));
  • 0

#7 gregwarner

gregwarner

    Obi Wan of Programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1586 posts
  • Location:Arkansas
  • Programming Language:C, Java, C++, C#, PHP, Transact-SQL

Posted 26 January 2012 - 11:35 AM

In any case, IEnumerable has a Union extension method.


Good to know. Do you happen to know how LinkedList implements this method? Is it done in O(1) or O(n) time?

EDIT: Just did some reading up on Union(). NOTE!!! Union produces a set with the duplicates removed! Look into it carefully before deciding whether to use it or not.
Documentation: Enumerable.Union(TSource) Method (IEnumerable(TSource), IEnumerable(TSource)) (System.Linq)

---------- Post added at 01:35 PM ---------- Previous post was at 01:27 PM ----------

foo.AddRange(bar.FindAll( x => foo.IndexOf(x.ToString()) == -1));


I don't believe that would do it in O(1) time like he is wanting. Also, FindAll() isn't defined in LinkedList, only List. Same goes for AddRange()
  • 0

ti-99-sig.png
Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law.
– Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid


#8 lespauled

lespauled

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1360 posts
  • Programming Language:C, C++, C#, JavaScript, PL/SQL, Delphi/Object Pascal, Visual Basic .NET, Pascal, Transact-SQL, Bash

Posted 26 January 2012 - 11:41 AM

What I was responding to was that the code with a lambda would do what a union would do in a list, hence the IndexOf condition.

If you want to all all items, you can do a foo.AddRange(bar)
  • 0

#9 gregwarner

gregwarner

    Obi Wan of Programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1586 posts
  • Location:Arkansas
  • Programming Language:C, Java, C++, C#, PHP, Transact-SQL

Posted 26 January 2012 - 11:42 AM

I have a further note about concatenating two Linked Lists. I found a thread over at StackOverflow about the exact same issue as we're talking about here. I believe this explains it concisely:

Yes, you have to loop, unfortunately. This is an O(n) operation - O(1) for each entry added. There's no risk of requiring a buffer to be resized and copied, etc - although of course garbage collection might do roughly that...

EDIT: Erich's comment suggests why you might think this is inefficient - why not just join the two lists together by updating the "next" pointer of the tail of the first list and the "prev" pointer of the head of the second? Well, think about what would happen to the second list... it would have changed as well.

Not only that, but what would happen to the ownership of those nodes? Each is essentially part of two lists now... but the LinkedListNode<T>.List property can only talk about one of them.

While I can see why you might want to do this in some cases, the way that the .NET LinkedList<T> type has been built basically prohibits it. I think this doc comment explains it best:

The LinkedList<T>) class does not support chaining, splitting, cycles, or other features that can leave the list in an inconsistent state.


Source:
.net - How does one add a LinkedList<T> to a LinkedList<T> in C#? - Stack Overflow

Looks like you're stuck with O(n) time for now. :(
  • 0

ti-99-sig.png
Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law.
– Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid






Also tagged with one or more of these keywords: linked list

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download