linkedlist

README

Linked List

---

What is it?

---

Linked list is a data structure that is a linear chain of data elements whose order is not given by their phyisical placement in memory. This structure is built up of nodes which point to the element ahead or behind this particular node (depending on the type of Linked List).

Types of Linked List implemented within this repository

Singly Linked List

Singly Linked List is a linked list in which a node only points to the next element. Some of the main applications of Singly Linked List are in the construction of fundamental data structures such as Stacks and Queues.

Doubly Linked List

Doubly Linked List is a linked list in which a node points to both the element ahead and behind the node. Any application which requires us to keep track of forward and backward information uses doubly linked list. For example, the feature of undo and redo are implemented using these doubly linked lists.

Cyclic Linked List AKA Looped Linked List

Looped Linked Lists are singly or doubly-linked that chase their own tail: A points to B, B points to C, C points to D, and D points to A. They are better suited for cyclic data such as train schedules. These lists are missing the first and last items. Therefore, it is necessary to introduce the concept of the current position.

This picture shows similar lists:

Documentation

Overview

Package linkedlist demonstrates different implementations on linkedlists.

Index

• func JosephusProblem(cl *Cyclic[int], k int) int
• type Cyclic
  • func NewCyclic[T any]() *Cyclic[T]
  • func (cl *Cyclic[T]) Add(val T)
  • func (cl *Cyclic[T]) Delete() bool
  • func (cl *Cyclic[T]) Destroy()
  • func (cl *Cyclic[T]) Rotate(places int)
  • func (cl *Cyclic[T]) Walk() *Node[T]
• type Doubly
  • func NewDoubly[T any]() *Doubly[T]
  • func (ll *Doubly[T]) AddAtBeg(val T)
  • func (ll *Doubly[T]) AddAtEnd(val T)
  • func (ll *Doubly[T]) Back() *Node[T]
  • func (ll *Doubly[T]) Count() int
  • func (ll *Doubly[T]) DelAtBeg() (T, bool)
  • func (ll *Doubly[T]) DelAtEnd() (T, bool)
  • func (ll *Doubly[T]) DelByPos(pos int) (T, bool)
  • func (ll *Doubly[T]) Display()
  • func (ll *Doubly[T]) DisplayReverse()
  • func (ll *Doubly[T]) Front() *Node[T]
  • func (ll *Doubly[T]) Init() *Doubly[T]
  • func (ll *Doubly[T]) MoveToBack(n *Node[T])
  • func (ll *Doubly[T]) Remove(n *Node[T]) T
  • func (ll *Doubly[T]) Reverse()
• type Node
  • func NewNode[T any](val T) *Node[T]
• type Singly
  • func NewSingly[T any]() *Singly[T]
  • func (ll *Singly[T]) AddAtBeg(val T)
  • func (ll *Singly[T]) AddAtEnd(val T)
  • func (ll *Singly[T]) CheckRangeFromIndex(left, right int) error
  • func (ll *Singly[T]) Count() int
  • func (ll *Singly[T]) DelAtBeg() (T, bool)
  • func (ll *Singly[T]) DelAtEnd() (T, bool)
  • func (ll *Singly[T]) DelByPos(pos int) (T, bool)
  • func (ll *Singly[T]) Display()
  • func (ll *Singly[T]) Reverse()
  • func (ll *Singly[T]) ReversePartition(left, right int) error

Functions

func JosephusProblem

func JosephusProblem(cl *Cyclic[int], k int) int

https://en.wikipedia.org/wiki/Josephus_problem This is a struct-based solution for Josephus problem.

Types

type Cyclic

type Cyclic[T any] struct {
	Size int
	Head *Node[T]
}

Cyclic Struct which cycles the linked list in this implementation.

func NewCyclic

func NewCyclic[T any]() *Cyclic[T]

Create new list.

func (*Cyclic[T]) Add

func (cl *Cyclic[T]) Add(val T)

Inserting the first node is a special case. It will point to itself. For other cases, the node will be added to the end of the list. End of the list is Prev field of current item. Complexity O(1).

func (*Cyclic[T]) Delete

func (cl *Cyclic[T]) Delete() bool

Delete the current item.

func (*Cyclic[T]) Destroy

func (cl *Cyclic[T]) Destroy()

Destroy all items in the list.

func (*Cyclic[T]) Rotate

func (cl *Cyclic[T]) Rotate(places int)

Rotate list by P places. This method is interesting for optimization. For first optimization we must decrease P value so that it ranges from 0 to N-1. For this we need to use the operation of division modulo. But be careful if P is less than 0. if it is - make it positive. This can be done without violating the meaning of the number by adding to it a multiple of N. Now you can decrease P modulo N to rotate the list by the minimum number of places. We use the fact that moving forward in a circle by P places is the same as moving N - P places back. Therefore, if P > N / 2, you can turn the list by N-P places back. Complexity O(n).

func (*Cyclic[T]) Walk

func (cl *Cyclic[T]) Walk() *Node[T]

Show list body.

type Doubly

type Doubly[T any] struct {
	Head *Node[T]
}

Doubly structure with just the Head Node We call it `Doubly` to make it easier to understand when calling this in peoples own local code to understand and experiment with this easily. For example, we can use gotools `go get` command to get this repository cloned inside the $GOPATH/src/github.com/FridaFino/goalgorithms (you can do this manually as well) and use the import statement as follows:

`import "github.com/FridaFino/goalgorithms/structure/linkedlist"`

and call linkedlist.Doubly to create a new doubly linked list.

func NewDoubly

func NewDoubly[T any]() *Doubly[T]

func (*Doubly[T]) AddAtBeg

func (ll *Doubly[T]) AddAtBeg(val T)

AddAtBeg Add a node to the beginning of the linkedlist

func (*Doubly[T]) AddAtEnd

func (ll *Doubly[T]) AddAtEnd(val T)

AddAtEnd Add a node at the end of the linkedlist

func (*Doubly[T]) Back

func (ll *Doubly[T]) Back() *Node[T]

func (*Doubly[T]) Count

func (ll *Doubly[T]) Count() int

Count Number of nodes in the linkedlist

func (*Doubly[T]) DelAtBeg

func (ll *Doubly[T]) DelAtBeg() (T, bool)

DelAtBeg Delete the node at the beginning of the linkedlist

func (*Doubly[T]) DelAtEnd

func (ll *Doubly[T]) DelAtEnd() (T, bool)

DetAtEnd Delete a node at the end of the linkedlist

func (*Doubly[T]) DelByPos

func (ll *Doubly[T]) DelByPos(pos int) (T, bool)

DelByPos deletes node at middle based on position in list and returns value. If empty or position of node is less than linked list length, returns false

func (*Doubly[T]) Display

func (ll *Doubly[T]) Display()

Display display the linked list

func (*Doubly[T]) DisplayReverse

func (ll *Doubly[T]) DisplayReverse()

DisplayReverse Display the linkedlist in reverse order

func (*Doubly[T]) Front

func (ll *Doubly[T]) Front() *Node[T]

func (*Doubly[T]) Init

func (ll *Doubly[T]) Init() *Doubly[T]

Init initializes double linked list

func (*Doubly[T]) MoveToBack

func (ll *Doubly[T]) MoveToBack(n *Node[T])

func (*Doubly[T]) Remove

func (ll *Doubly[T]) Remove(n *Node[T]) T

func (*Doubly[T]) Reverse

func (ll *Doubly[T]) Reverse()

Reverse Reverse the order of the linkedlist

type Node

type Node[T any] struct {
	Val  T
	Prev *Node[T]
	Next *Node[T]
}

Node Structure representing the linkedlist node. This node is shared across different implementations.

func NewNode

func NewNode[T any](val T) *Node[T]

Create new node.

type Singly

type Singly[T any] struct {

	// Note that Node here holds both Next and Prev Node
	// however only the Next node is used in Singly methods.
	Head *Node[T]
	// contains filtered or unexported fields
}

Singly structure with length of the list and its head

func NewSingly

func NewSingly[T any]() *Singly[T]

NewSingly returns a new instance of a linked list

func (*Singly[T]) AddAtBeg

func (ll *Singly[T]) AddAtBeg(val T)

AddAtBeg adds a new snode with given value at the beginning of the list.

func (*Singly[T]) AddAtEnd

func (ll *Singly[T]) AddAtEnd(val T)

AddAtEnd adds a new snode with given value at the end of the list.

func (*Singly[T]) CheckRangeFromIndex

func (ll *Singly[T]) CheckRangeFromIndex(left, right int) error

func (*Singly[T]) Count

func (ll *Singly[T]) Count() int

Count returns the current size of the list.

func (*Singly[T]) DelAtBeg

func (ll *Singly[T]) DelAtBeg() (T, bool)

DelAtBeg deletes the snode at the head(beginning) of the list and returns its value. Returns false if the list is empty.

func (*Singly[T]) DelAtEnd

func (ll *Singly[T]) DelAtEnd() (T, bool)

DelAtEnd deletes the snode at the tail(end) of the list and returns its value. Returns false if the list is empty.

func (*Singly[T]) DelByPos

func (ll *Singly[T]) DelByPos(pos int) (T, bool)

DelByPos deletes the node at the middle based on position in the list and returns its value. Returns false if the list is empty or length is not more than given position

func (*Singly[T]) Display

func (ll *Singly[T]) Display()

Display prints out the elements of the list.

func (*Singly[T]) Reverse

func (ll *Singly[T]) Reverse()

Reverse reverses the list.

func (*Singly[T]) ReversePartition

func (ll *Singly[T]) ReversePartition(left, right int) error

ReversePartition Reverse the linked list from the ath to the bth node