Go - Creating Linked Lists

Problem: You want to create a linked list data structure.

Solution: Create an element struct that has a pointer to the next element. Wrap another struct around the first element to create a linked list.

A linked list is a linear collection of elements that has each element pointing to the next element. This is different from a list because in lists the elements are next to each other (incrementing the index of the current element will give you access to the next element) while for a linked list this is not necessarily so. As a result, inserting or removing an element is faster because you don’t need to restructure the data structure, unlike in a list. On the other hand, accessing random elements in a linked list is slower because elements are not indexed, so you need to iterate through the elements until the correct one is found.

The functions for the singly linked list are:
Add
• Add a new element to the end of the linked list.
Insert
• Insert a new element into a specific position within the linked list.
Delete
• Remove a specific element from the linked list.
Find
• Find and return an element from the linked list.

In a linked list, you will use two structs — one to represent the data structure, LinkedList , and another to represent an element in the data structure, Element :

import   "golang.org/x/exp/constraints" 

type   Element [ T   constraints . Ordered ]   struct   { 
      value   T 
      next    * Element [ T ] 
} 

type   LinkedList [ T   constraints . Ordered ]   struct   { 
      head   * Element [ T ] 
      size   int 
}

You need to do this because each element in the linked list points to the next; therefore it needs to keep a pointer to the next. You create an Element struct to represent an element, with a next field pointing to the next element. The Element struct also has a value, which is of type T , constrained by the constraints.Ordered type. This means you can use the ordering operators (<, >, <=, >=) on Element values.

You create a LinkedList struct to keep track of the head of the linked list and its size. You need this struct to associate all the linked list functions.

func   ( l   * LinkedList [ T ])   Add ( el   * Element [ T ])   { 
      if   l . head   ==   nil   { 
          l . head   =   el 
      }   else   { 
          el . next   =   l . head 
          l . head   =   el 
      } 
      l . size ++ 
}

func   ( l   * LinkedList [ T ])   Insert ( el   * Element [ T ],   marker   T )   error   { 
      for   current   :=   l . head ;   current . next   !=   nil ;   current   =   current . next   { 
          if   current . value   ==   marker   { 
              el . next   =   current . next 
              current . next   =   el 
              l . size ++ 
              return   nil 
          } 
      } 
      return   errors . New ( "element  not  found" ) 
}

func   ( l   * LinkedList [ T ])   Delete ( el   * Element [ T ])   error   { 
      prev   :=   l . head 
      current   :=   l . head 
      for   current   !=   nil   { 
          if   current . value   ==   el . value   { 
              if   current   ==   l . head   { 
                  l . head   =   current . next 
              }   else   { 
                  prev . next   =   current . next 
              } 
              l . size - - 
              return   nil 
          } 
          prev   =   current 
          current   =   current . next 
      } 
      return   errors . New ( "element  not  found" ) 

}

func   ( l   * LinkedList [ T ])   Find ( value   T )   ( el   * Element [ T ],   err   error )   { 
      for   current   :=   l . head ;   current . next   !=   nil ;   current   =   current . next   { 
          if   current . value   ==   value   { 
              el   =   current 
              break 
          } 
      } 
      if   el   ==   nil   { 
          err   =   errors . New ( "element  not  found" ) 
      } 
      return 
}

func   ( l   * LinkedList [ T ])   List ()   ( list   [] * Element [ T ])   { 
      if   l . head   ==   nil   { 
          return   [] * Element [ T ]{} 
      } 
      for   current   :=   l . head ;   current   !=   nil ;   current   =   current . next   { 
          list   =   append ( list ,   current ) 
      } 
      return 
}

func   ( l   * LinkedList [ T ])   IsEmpty ()   bool   { 
      return   l . size   ==   0 
} 

func   ( l   * LinkedList [ T ])   Size ()   int   { 
      return   l . size 
}

The standard library has a container package with a few data structure implementations, and it includes a doubly linked list. If you’re looking for a linked list, this would be a good place to start.