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 demonstates different implementations on linkedlists.

Index

• func JosephusProblem(cl *Cyclic, k int) int
• type Cyclic
  • func NewCyclic() *Cyclic
  • func (cl *Cyclic) Add(val interface{})
  • func (cl *Cyclic) Delete() bool
  • func (cl *Cyclic) Destroy()
  • func (cl *Cyclic) Rotate(places int)
  • func (cl *Cyclic) Walk() *Node
• type Doubly
  • func NewDoubly() *Doubly
  • func (ll *Doubly) AddAtBeg(val interface{})
  • func (ll *Doubly) AddAtEnd(val interface{})
  • func (ll *Doubly) Count() interface{}
  • func (ll *Doubly) DelAtBeg() interface{}
  • func (ll *Doubly) DelAtEnd() interface{}
  • func (ll *Doubly) Display()
  • func (ll *Doubly) DisplayReverse()
  • func (ll *Doubly) Reverse()
• type Node
  • func NewNode(val interface{}) *Node
• type Singly
  • func NewSingly() *Singly
  • func (ll *Singly) AddAtBeg(val interface{})
  • func (ll *Singly) AddAtEnd(val int)
  • func (ll *Singly) Count() int
  • func (ll *Singly) DelAtBeg() interface{}
  • func (ll *Singly) DelAtEnd() interface{}
  • func (ll *Singly) Display()
  • func (ll *Singly) Reverse()

Functions

func JosephusProblem

func JosephusProblem(cl *Cyclic, k int) int

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

Types

type Cyclic

type Cyclic struct {
	Size int
	Head *Node
}

Cyclic Struct which cycles the linked list in this implementation.

func NewCyclic

func NewCyclic() *Cyclic

Create new list.

func (*Cyclic) Add

func (cl *Cyclic) Add(val interface{})

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) Delete

func (cl *Cyclic) Delete() bool

Delete the current item.

func (*Cyclic) Destroy

func (cl *Cyclic) Destroy()

Destroy all items in the list.

func (*Cyclic) Rotate

func (cl *Cyclic) 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) Walk

func (cl *Cyclic) Walk() *Node

Show list body.

type Doubly

type Doubly struct {
	Head *Node
}

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/TheAlgorithms/Go (you can do this manually as well) and use the import statement as follows:

`import "github.com/TheAlgorithms/Go/structure/linkedlist"`

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

func NewDoubly

func NewDoubly() *Doubly

func (*Doubly) AddAtBeg

func (ll *Doubly) AddAtBeg(val interface{})

AddAtBeg Add a node to the beginning of the linkedlist

func (*Doubly) AddAtEnd

func (ll *Doubly) AddAtEnd(val interface{})

AddAtEnd Add a node at the end of the linkedlist

func (*Doubly) Count

func (ll *Doubly) Count() interface{}

Count Number of nodes in the linkedlist

func (*Doubly) DelAtBeg

func (ll *Doubly) DelAtBeg() interface{}

DelAtBeg Delete the node at the beginning of the linkedlist

func (*Doubly) DelAtEnd

func (ll *Doubly) DelAtEnd() interface{}

DetAtEnd Delete a node at the end of the linkedlist

func (*Doubly) Display

func (ll *Doubly) Display()

Display diplay the linked list

func (*Doubly) DisplayReverse

func (ll *Doubly) DisplayReverse()

DisplayReverse Display the linkedlist in reverse order

func (*Doubly) Reverse

func (ll *Doubly) Reverse()

Reverse Reverse the order of the linkedlist

type Node

type Node struct {
	Val  interface{}
	Prev *Node
	Next *Node
}

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

func NewNode

func NewNode(val interface{}) *Node

Create new node.

type Singly

type Singly struct {

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

Singly structure with length of the list and its head

func NewSingly

func NewSingly() *Singly

NewSingly returns a new instance of a linked list

func (*Singly) AddAtBeg

func (ll *Singly) AddAtBeg(val interface{})

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

func (*Singly) AddAtEnd

func (ll *Singly) AddAtEnd(val int)

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

func (*Singly) Count

func (ll *Singly) Count() int

Count returns the current size of the list.

func (*Singly) DelAtBeg

func (ll *Singly) DelAtBeg() interface{}

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

func (*Singly) DelAtEnd

func (ll *Singly) DelAtEnd() interface{}

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

func (*Singly) Display

func (ll *Singly) Display()

Display prints out the elements of the list.

func (*Singly) Reverse

func (ll *Singly) Reverse()

Reverse reverses the list.