Understanding the Modern Generic LinkedList Collection Class
Dive into the modern implementation of the Generic LinkedList Collection class, which allows you to efficiently manage data in a chain of nodes. Learn about creating, adding, removing, and iterating through nodes, offering a versatile way to handle data without the need for manual implementation. Explore the key methods like AddFirst, AddLast, RemoveFirst, RemoveLast, and more to enhance your understanding of this powerful data structure.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
The Generic LinkedList<> Collection class Modern Collections Classes
Generic LinkedList<> Overview
LinkedList<> stores data in a chain of nodes The Stack static void Main(string[] args) Main() { LinkedList<int> numList = new LinkedList<int>(); numList numList.AddFirst(10); numList.AddLast(20); LinkedList<int> object numList.AddLast(30); Internal reference to first and last nodes in the list foreach( int num in numList) { null Console.WriteLine(num); } 30 10 20 null
Overview LinkedList<> class allows you to create, add, remove, and move nodes within the list The Stack Main() This saves you time by not having to implement (write) it yourself numList You can use this to access items one at a time (as you walk along the chain). You can get the individual nodes themselves You can quickly add / remove individual items (as they spliced into / out of the chain) LinkedList<int> You CANNOT jump to a location quickly (in contrast to arrays and the basic List) First Last 2 1
Lets start by looking at code that doesnt interact with the nodes themselves
AddFirst() method, foreach loop The Stack // Part 1 Main() Create a LinkedList of int s Then add a couple ints LinkedList<int> numList = new LinkedList<int>(); numList numList.AddFirst(1); numList.AddFirst(2); Foreach can be used to access every element in the list foreach (int num in numList) LinkedList<int> { First Last Console.WriteLine(num); OUTPUT: 2 1 null } null 2 1
AddLast() method The Stack OUTPUT: List contents: 2, 1, 3, 4, 5 // Part 2 Main() numList.AddLast(3); numList numList.AddLast(4); numList.AddLast(5); PrintList(numList); LinkedList<int> First Last 2 1 3 4 5
RemoveFirst(), RemoveLast(), Remove() OUTPUT: List contents: 1, 3, 4 List contents: 1, 4 The Stack // Part 3 Main() numList.RemoveFirst(); numList numList.RemoveLast(); PrintList(numList); numList.Remove(3); // NOTE: Removing via the VALUE // Need to find value O(N) LinkedList<int> First Last PrintList(numList); 2 1 3 4 5
Now lets look at code that chooses to be uses the nodes directly
.First, .Next, .Previous instance variables OUTPUT: First node s value: 1 Next node s value: 4 Previous node s value: null // Part 4 LinkedListNode<int> refToNode; // no node created yet refToNode = numList.First; Console.WriteLine( First node s value: {0}", refToNode.Value); refToNode if (refToNode.Next != null) Console.WriteLine("Next node s value: {0}", refToNode.Next.Value); LinkedList<int> else First Last Console.WriteLine("Next node s value: null"); if (refToNode.Previous != null ) Console.WriteLine("Previous node s value: {0}", refToNode.Previous.Value); 1 4 else Console.WriteLine("Previous node s value: null");
AddAfter(), AddBefore() OUTPUT: List contents: 1, 6, 4 List contents: 7, 1, 6, 4 // Part 5 numList.AddAfter(refToNode, 6); PrintList(numList); numList.AddBefore(refToNode, 7); PrintList(numList); LinkedList<int> First Last refToNode 7 1 6 4
Remove(node) OUTPUT: refToNode points to 1 refToNode STILL points to 1 First list: List contents: 7, 6, 4 // Part 6 Console.WriteLine("refToNode points to {0}", refToNode.Value); numList.Remove(refToNode); // NOTE: Removing via the NODE // Don t have to find, so it s O(1) LinkedList<int> Console.WriteLine("refToNode STILL points to {0}", refToNode.Value); First Last refToNode Console.Write("First list: "); PrintList(numList); 1 7 6 4
Moving a node to a different list is fine OUTPUT: Second list: List contents: 1 // Part 7 LinkedList<int> secondList = new LinkedList<int>(); secondList.AddFirst(refToNode); Console.Write("Second list: "); PrintList(secondList); LinkedList<int> LinkedList<int> First Last First Last refToNode null null 7 6 4 1
Find() OUTPUT: Found 4 Did NOT find 8 // Part 8 LinkedListNode<int> findIt = numList.Find(4); if (findIt != null) LinkedList<int> Console.WriteLine("Found 4"); First Last else Console.WriteLine("Did NOT find 4"); findIt LinkedListNode<int> findIt = numList.Find(8); if (findIt != null) Console.WriteLine("Found 8"); null 7 6 4 else Console.WriteLine("Did NOT find 8");
Methods You Must Memorize
Useful Methods And Properties The Count property (how many items are in the list) AddFirst(), AddLast(): Adding new values, or a LinkedListNode, to either end of the list RemoveFirst(), RemoveLast(), Remove(T) foreach loop .First, .Last properties on the List .Next, .Previous, .Value properties on the LinkedListNode Find() AddAfter(), AddBefore() Add value, or LLNode, to the list Remove(LinkedListNode<>)
More Useful Methods Contains: Find an element by doing a linear search LinkedList doesn t have a Sort method LinkedList doesn t have a BinarySearch Because you can t jump to an arbitrary spot Specifically, it s O(N) to jump to the middle So even if the list was sorted it would take O(N lgN) to execute Or you could do a linear search for O(N)
How is List<> implemented? How can we figure this out on our own?
Search The Web This particular data structure is very public about how it s structured. Interesting to note that you re not allowed to manipulate the internal structures yourself You can call AddBefore to add a node before an existing node HOWEVER, you can t change First/Last/Next/Previous yourself
Method Running Times in Big Oh notation
Running times for list-based Add methods The running time for AddFirst( valueToAdd ) : This method is an O(1) operation. , according to the docs on MSDN Because you re adding the new element to the very start of the list, and because the LinkedList class keeps track of First, it takes a constant amount of time add the new node in In other words, you re adding a single node from a known location, as demonstrated previously The running time for AddLast( valueToAdd ): This method is an O(1) operation. Similar to AddFirst, you re adding the new node to the end of the list, and the list tracks the last node (as you ve seen in previous pictures) In other words, you re adding a single node from a known location, as demonstrated previously
Running times for node-based Add methods The running time for AddAfter(LinkedListNode<>, valueToAdd): This method is an O(1) operation. , according to the docs on MSDN Because you re adding the new element to the very start of the list, and because the LinkedList class keeps track of First, it takes a constant amount of time add the new node in In other words, you re adding a single node from a known location, as demonstrated previously The running time for AddBefore(LinkedListNode<>, valueToAdd): This method is an O(1) operation. Similar to AddFirst, you re adding the new node to the end of the list, and the list tracks the last node (as you ve seen in previous pictures) In other words, you re adding a single node from a known location, as demonstrated previously
Running times for Removes: The running time for RemoveFirst() and for RemoveLast() is O(1) For both, the ONLY remark is: This method is an O(1) operation. You re removing a single node from a known location, as demonstrated previously Remove(T) is O(N), because it has to walk through the list to find the thing to remove Example: numList.Remove(3); This method performs a linear search; therefore, this method is an O(n) operation, where n is Count. You need to search through the list to find the thing to remove, as demonstrated previously Remove(LinkedListNode<T>) is O(1) Example: numList.Remove(refToNode); This method is an O(1) operation. You re removing a single node from a known location, as demonstrated previously
Running times: What the docs say Find(T) is O(N), because it has to walk through the list to find the thing to return This method performs a linear search; therefore, this method is an O(n) operation, where n is Count. You need to search through the list to find the thing to remove, as demonstrated previously
When to use LinkedList<>
Why /why not use a LinkedList<>? It s good when you want to access the values sequentially (i.e., walk through the values in order) and you want to add new items into the middle as you walk through the list Fast (constant-time) insertion or removal But only at the start/end of the list, or near a node that you previously found In contrast, the array-based List<> can only add things to the end O(1) for adding to the end O(N) to shuffle everything down when adding to the middle) Slower (linear-time) access to the elements The best you can do for finding an element is O(N) / linear time Each <thing> we store requires a node, so it s bad for storing a lot of small things For example, storing a lot of individual characters would be very inefficient
