Linked list stuff in a modern environment

So recently somebody asked about this and seemed surprised when I said that owing to the availability of lots of lists and collection classes in modern frameworks, I had not coded a linked list in a couple of decades, at least not since I completed my BSc (finished in 1996 while employed by IBM). So anyways, I decided to include them in this blog series just to show I can do it if I have to! I suppose it still makes sense to think about collection class implementation every now and then - it may be very useful in some future role if performance tweaking on structures like these becomes important. One caveat is that I have just included these quickly, and so haven't really optimised or thought about the "best" way to do the following methods - just made ones that work (without much testing).

 

For these examples I have used a Single Linked List. This class defines it and the following method is used just to display the list contents of the list:

  class SLLNode
 {
 public int value;
 
 public SLLNode pNext;
 
 public SLLNode(int val)
 {
 value = val;
 pNext = null;
 }
 }
 
 private static void DisplayLL(SLLNode current)
 {
 while (current != null)
 {
 Console.WriteLine("Node value {0}", current.value);
 current = current.pNext;
 }
 }

 

Copying a Single Linked List

Can be little confusing as you're effectively stepping through two lists, the existing list and the one you are creating as you go:

 

  private static SLLNode CopySLL(SLLNode n1)
 {
 SLLNode current = n1;
 
 
 SLLNode newHead = new SLLNode(n1.value);
 SLLNode prev = newHead;
 
 while (current != null)
 {
 current = current.pNext; //old list
 
 if (current != null)
 {
 SLLNode newNode = new SLLNode(current.value);
 prev.pNext = newNode;
 prev = prev.pNext;
 }
 }
 
 DisplayLL(newHead);
 return newHead;
 }

Sorting a Single Linked List

Just using a simple bubble sort here for a list with integer values in the payload. I'm writing this on a tired Sunday evening, so feel free to suggest "improvements"!

 

  private static void SortSLL(SLLNode head)
 {
 SLLNode current;
 int swaps = 1;
 
 while (swaps > 0)
 {
 current = head;
 swaps = 0;
 while (current != null)
 {
 SLLNode next = current.pNext;
 
 if (next != null)
 {
 if (current.value > next.value)
 {
 int tmp = current.value;
 current.value = next.value;
 next.value = tmp;
 swaps++;
 }
 }
 current = next; //move along
 }
 }
 }

 

Reverse a Single Linked List

Walk the list, reversing the "pNext" pointers as you go - just need to remember not to orphan any nodes, and to set the original head's "next" pointer to point to null as it becomes the tail

 

  private static SLLNode ReverseSLL(SLLNode head)
 {
 SLLNode current = head;
 
 SLLNode prev;
 
 SLLNode next = current.pNext; 
 
 while (next != null)
 {
 prev = current;
 current = next;
 next = current.pNext;
 current.pNext = prev;
 }
 head.pNext = null;
 
 return current;
 }