[Go] Linked List - Singly Linked List - Design Linked List

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

• MyLinkedList() Initializes the MyLinkedList object.
• int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
• void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
• void addAtTail(int val) Append a node of value val as the last element of the linked list.
• void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
• void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

 

Example 1:

Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]

Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

 

Constraints:

• 0 <= index, val <= 1000
• Please do not use the built-in LinkedList library.
• At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

My code

type MyLinkedList struct {
	next *MyLinkedList
	val  int
}

func Constructor() MyLinkedList {
	return MyLinkedList{val: -1}
}

func (this *MyLinkedList) Get(index int) int {
	node := this
	for i := 0; i < index; i++ {
		if node.next != nil {
			node = node.next
		} else {
			return -1
		}

	}
	return node.val
}

func (this *MyLinkedList) AddAtHead(val int) {
	node := *this
	*this = MyLinkedList{val: val, next: &node}
}

func (this *MyLinkedList) AddAtTail(val int) {
	for this.next != nil {
		this = this.next
	}
	new := MyLinkedList{val: this.val}
	*this = MyLinkedList{val: val, next: &new}

}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index == 0 && this.val != -1 {
		this.AddAtHead(val)
		return
	} else if index == 1 && this.val == -1 {
		return
	}
	node := this
	for i := 0; i < index; i++ {
		// if reflect.DeepEqual(*node, MyLinkedList{}) {
		// 	return
		// }
		if node.next == nil && index-1 == i {
			this.AddAtTail(val)
			return
		} else if node.next == nil {
			return
		}

		node = node.next
	}

	new := *node
	new = MyLinkedList{node.next, node.val}
	*node = MyLinkedList{&new, val}

}

func (this *MyLinkedList) DeleteAtIndex(index int) {
	node := this
	if index == 0 && node.next == nil {
		*this = MyLinkedList{val: -1}
		return
	}
	for i := 0; i < index; i++ {
		if node.next != nil {
			node = node.next
		} else {
			return
		}

	}
	if node.next == nil {
		*node = MyLinkedList{val: -1}
		return
	}
	if node.next.next != nil {
		*node = MyLinkedList{node.next.next, node.next.val}
	} else {
		*node = MyLinkedList{val: node.next.val}
	}

}

 

sample 16 ms submission

sample 16 ms submission
type MyLinkedList struct {
    val int
    next *MyLinkedList
}


func Constructor() MyLinkedList {
    return MyLinkedList{
        val: 0,
        next: nil,
    }
}


func (this *MyLinkedList) Get(index int) int {
    if index < 0 {
        return -1
    }
    
    h := this
    for h != nil && index >= 0 {
        h = h.next
        index--
    }
    
    if h != nil {
        return h.val
    }
    
    return -1
}


func (this *MyLinkedList) AddAtHead(val int)  {
    n := &MyLinkedList {
        val: val,
        next: this.next,
    }
    
    this.next = n
}


func (this *MyLinkedList) AddAtTail(val int)  {
    h := this
    
    for h.next != nil {
        h = h.next
    }
    
    h.next = &MyLinkedList{
        val: val,
        next: nil,
    }
}


func (this *MyLinkedList) AddAtIndex(index int, val int)  {
    if index < 0 {
        return
    }
    
    prev, h := this, this.next
    for h != nil && index > 0 {
        prev = h
        h = h.next
        index--
    }
    
    if index == 0 {
        prev.next = &MyLinkedList{
            val: val,
            next: h,
        }
    }
}


func (this *MyLinkedList) DeleteAtIndex(index int)  {
    if index < 0 {
        return
    }
    
    prev, h := this, this.next
    for h != nil && index > 0 {
        prev = h
        h = h.next
        index--
    }
    
    if index == 0 && h != nil{
        prev.next = h.next
    }
}

sample 20 ms submission

type node struct {
    val int
    next *node
}

type MyLinkedList struct {
    head *node
}


func Constructor() MyLinkedList {
    return MyLinkedList{}    
}


func (this *MyLinkedList) Get(index int) int {
    if this.head == nil {
        return -1
    }
    
    for counter, cur := 0, this.head; cur != nil; counter, cur = counter+1, cur.next {
        if counter == index {
            return cur.val
        }
    }
    
    return -1  
}


func (this *MyLinkedList) AddAtHead(val int)  {
    cur := &node {val: val}
    
    if this.head == nil {
        this.head = cur
    }  else {
        cur.next = this.head
        this.head = cur
    }  
}


func (this *MyLinkedList) AddAtTail(val int)  {
    cur := &node{val : val}
    
    if this.head == nil {
        this.head = cur
    } else {
        next := this.head
        for next.next != nil {
            next = next.next
        }   
        next.next = cur
    }
}


func (this *MyLinkedList) AddAtIndex(index int, val int)  {
    if this.head == nil {
        if index == 0 {
            this.AddAtTail(val)
        }
        
        return
    } 
    
    counter := 0
    for cur := this.head; cur != nil; counter, cur = counter+1, cur.next {
        if counter == index {
            tmp := *cur
            cur.val = val
            cur.next = &tmp
        }
    }
    
    if counter == index {
        this.AddAtTail(val)
    }
}


func (this *MyLinkedList) DeleteAtIndex(index int)  {
    if this.head == nil {
        return
    } 
    if index == 0 {
        this.head = this.head.next
        return
    }
    
    counter := 0
    prev := this.head
    cur := this.head
    for cur != nil {
        if counter == index {
            prev.next = cur.next
            break    
        }
        prev = cur
        cur = cur.next
        counter++
    }   
}

sample 21 ms submission

type MyLinkedList struct {
	root *ListNode
}

func Constructor() MyLinkedList {
	return MyLinkedList{nil}
}

func (this *MyLinkedList) Get(index int) int {
    val:=-1
	for i, head := 0, this.root; head != nil; head, i = head.Next, i+1 {
		if i == index {
			val = head.Val
			break
		}
	}
	return val
}

func (this *MyLinkedList) AddAtHead(val int) {
	node := &ListNode{val, this.root}
	node.Next = this.root
	this.root = node

}

func (this *MyLinkedList) AddAtTail(val int) {

	node := &ListNode{val, nil}
	if this.root == nil {
		this.root = node
		return
	}

	head := this.root
	for ; head.Next != nil; head = head.Next {
	}
	head.Next = node
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {

	node := &ListNode{Val: val}
	if this.root == nil {
		if index == 0 {
			this.root = node
		}

		return
	}

	if index == 0 {
		node.Next = this.root
		this.root = node
		return
	}

	i := 0
	head := this.root
	for ; head.Next != nil; head, i = head.Next, i+1 {
		if i == index-1 {
			node.Next = head.Next
			head.Next = node
			return
		}
	}
	if i+1 == index {
		head.Next = node
	}

}

func (this *MyLinkedList) DeleteAtIndex(index int) {

	if this.root == nil {
		return
	}

	if index == 0 {
		this.root = this.root.Next
		return
	}

	for i, head := 0, this.root; head.Next != nil; head, i = head.Next, i+1 {
		if i == index-1 {
			head.Next = head.Next.Next
			return
		}
	}

}

func (ml MyLinkedList) GetList() []int {
	result := []int{}
	head := ml.root
	for head != nil {
		result = append(result, head.Val)
		head = head.Next
	}
	return result
}

sample 22 ms submission

type MyLinkedList struct {
    head *Node
	tail *Node
}


func Constructor() MyLinkedList {
    return MyLinkedList{}
    
}


func (ll *MyLinkedList) Get(index int) int {
    n := ll.get(index)
	if n == nil {
		return -1
	}
	return n.Value
}


func (ll *MyLinkedList) AddAtHead(val int)  {
    n := Node{Value: val, Next: ll.head}
	ll.head = &n
	if ll.tail == nil {
		ll.tail = ll.head
	}
}


func (ll *MyLinkedList) AddAtTail(val int)  {
    n := Node{Value: val}
	if ll.tail == nil {
		ll.head = &n
		ll.tail = &n
	} else {
		ll.tail.Next = &n
		ll.tail = &n
	}
}


func (ll *MyLinkedList) AddAtIndex(index int, val int)  {
    if index == 0 {
		ll.head = &Node{Value: val, Next: ll.head}
		return
	}
	prev := ll.get(index - 1)
	if prev == nil {
		return
	}
	next := prev.Next
	prev.Next = &Node{Value: val, Next: next}
	if next == nil {
		ll.tail = prev.Next
	}
}


func (ll *MyLinkedList) DeleteAtIndex(index int)  {
    if index == 0 {
		if ll.head != nil {
			ll.head = ll.head.Next
		}
	}
	prev := ll.get(index - 1)
	if prev == nil || prev.Next == nil {
		return
	}
	curr := prev.Next
	if curr.Next == nil {
		prev.Next = nil
		ll.tail = prev
		return
	}
	prev.Next = curr.Next
}

func (ll *MyLinkedList) get(index int) *Node {
	var c int
	n := ll.head
	for n != nil {
		if c == index {
			return n
		}
		n = n.Next
		c++
	}
	return nil
}

type Node struct {
	Value int
	Next  *Node
}

sample 24 ms submission

type node struct {
    val int
    next, prev *node
}

type MyLinkedList struct {
    head, tail *node
    size int
}


func Constructor() MyLinkedList {
    return MyLinkedList{}
}


func (this *MyLinkedList) Get(index int) int {
    p := this.getNode(index)
    if p == nil {
        return -1
    }
    return p.val
}


func (this *MyLinkedList) AddAtHead(val int)  {
    n := &node{
        val: val,
    }
    this.size++
    if this.head == nil {
        this.head = n
        this.tail = n
        return
    }
    n.next = this.head
    this.head.prev = n
    this.head = n
}


func (this *MyLinkedList) AddAtTail(val int)  {
    n := &node{
        val: val,
    }
    this.size++
    if this.tail == nil {
        this.head = n
        this.tail = n
        return
    }
    
    this.tail.next = n
    n.prev = this.tail
    this.tail = n
}


func (this *MyLinkedList) AddAtIndex(index int, val int)  {
    switch {
    case index == 0:
        this.AddAtHead(val)
    case index == this.size:
        this.AddAtTail(val)
    case index > 0 && index < this.size:
        p := this.getNode(index - 1)
        this.size++
        n := &node{
            val: val,
        }
        n.next = p.next
        n.prev = p
        p.next.prev = n
        p.next = n
    }
}


func (this *MyLinkedList) DeleteAtIndex(index int)  {
    // this.print()
    if index < 0 || index >= this.size {
        return
    }
    this.size--
    p := this.getNode(index)
    // fmt.Println(p, index)
    if p == this.head {
        this.head = this.head.next
        if this.head != nil {
            this.head.prev = nil
        }
    }
    
    if p == this.tail {
        this.tail = this.tail.prev
        if this.tail != nil {
            this.tail.next = nil
        }
    }
    
    if p.prev != nil {
        p.prev.next = p.next
    }
    if p.next != nil {
        p.next.prev = p.prev
    }
}

func (this *MyLinkedList) getNode(index int) *node {
    p := this.head
    for i := 0; i < index && p != nil; p = p.next{
        i++
    }
    return p
}

func (this *MyLinkedList) print() {
    fmt.Println(this.head)
    fmt.Println(this.tail)
    for p := this.head; p != nil; p = p.next {
        fmt.Println(p)
    }
    fmt.Println("==========")
}

sample 25 ms submission

type SLLNode struct {
    next *SLLNode
    val int
}

type MyLinkedList struct {
    head *SLLNode
    size int
}


func Constructor() MyLinkedList {
    list := MyLinkedList{
        head: &SLLNode{val: -1},
    }
    return list
}


func (this *MyLinkedList) Get(index int) int {
    if index < 0 || index >= this.size {
        return -1
    }
    cur := this.head
    for i := 0; i <= index; i++ {
        cur = cur.next
    }
    return cur.val
}


func (this *MyLinkedList) AddAtHead(val int)  {
    this.AddAtIndex(0, val)
}


func (this *MyLinkedList) AddAtTail(val int)  {
    this.AddAtIndex(this.size, val)
}


func (this *MyLinkedList) AddAtIndex(index int, val int)  {
    if index < 0 || index > this.size {
        return
    }
    prev := this.head
    for i := 0; i < index; i++ {
        prev = prev.next
    }
    newNode := &SLLNode{next: prev.next, val: val}
    prev.next = newNode
    this.size++
}


func (this *MyLinkedList) DeleteAtIndex(index int)  {
    if index < 0 || index >= this.size {
        return
    }
    prev := this.head
    for i := 0; i < index; i++ {
        prev = prev.next
    }
    prev.next = prev.next.next
    this.size--
}

sample 26 ms submission

type node struct {
    v int
    n *node
    p *node
}

type MyLinkedList struct {
    h *node
    t *node
    l int
}


func Constructor() MyLinkedList {
    return MyLinkedList{}
}

func (this *MyLinkedList) getAtIndex(index int) *node {
    if index < 0 || index >= this.l {
        return nil
    }
     var (
        i int
        n *node
    )
    if this.l - index > index {
        for i, n = 0, this.h; i != index; i, n = i+1, n.n {}
    } else {
        for i, n = this.l-1, this.t; i != index; i, n = i-1, n.p {}
    }
    return n
}

func (this *MyLinkedList) Get(index int) int {
    n := this.getAtIndex(index)
    if n == nil {
        return -1
    }
    return n.v
}


func (this *MyLinkedList) AddAtHead(val int)  {
    this.AddAtIndex(0, val)
}


func (this *MyLinkedList) AddAtTail(val int)  {
    this.AddAtIndex(this.l, val)
}


func (this *MyLinkedList) AddAtIndex(index int, val int) {
    var p, n *node
    if index == this.l {
        p = this.t
    } else {
        n = this.getAtIndex(index)
        if n == nil {
            return
        }
        p = n.p
    }
    c := &node{v: val, p: p, n: n}
    if n == this.h {
        this.h = c
    }
    if p == this.t {
        this.t = c
    }
    if n != nil {
        n.p = c
    }
    if p != nil {
        p.n = c
    }
    this.l++
}


func (this *MyLinkedList) DeleteAtIndex(index int)  {
    c := this.getAtIndex(index)
    if c == nil {
        return
    }
    p, n := c.p, c.n
    if p != nil {
        p.n = n
    }
    if n != nil {
        n.p = p
    }
    if c == this.h {
        this.h = n
    }
    if c == this.t {
        this.t = p
    }
    this.l--
}

sample 27 ms submission

type LinkedNode struct {
	val  int
	next *LinkedNode
	prev *LinkedNode
}

type MyLinkedList struct {
	head, tail *LinkedNode
}

func Constructor() MyLinkedList {
	return MyLinkedList{nil, nil}
}

func (this *MyLinkedList) Get(index int) int {
	if index < 0 {
		return -1
	}

	node, _ := this.getNode(index)
	if node == nil {
		return -1
	}
	return node.val

}

func (this *MyLinkedList) getNode(index int) (*LinkedNode, int) {
	if index < 0 {
		i := -1
		n := this.head
		for n != nil && i > index {
			n = n.prev
			i--
		}
		return n, i
	} else {
		i := 0
		n := this.head
		for n != nil && i < index {
			n = n.next
			i++
		}
		return n, i
	}
}

func (this *MyLinkedList) AddAtHead(val int) {
	if this.head == nil {
		// add node to empty list
		this.head = &LinkedNode{val: val, next: nil, prev: nil}
		this.tail = this.head
	} else {
		n := &LinkedNode{val: val, next: this.head, prev: nil}
		this.head.prev = n
		this.head = n
	}
}

func (this *MyLinkedList) AddAtTail(val int) {
	if this.tail == nil {
		this.AddAtHead(val)
	} else {
		n := &LinkedNode{val: val, next: nil, prev: this.tail}
		this.tail.next = n
		this.tail = n
	}
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index == 0 {
		this.AddAtHead(val)
	} else {
		node, i := this.getNode(index)
		if node == nil {
			if i == index {
				this.AddAtTail(val)
			}
		} else {
			// add new node before "node"
			n := &LinkedNode{val: val, next: node, prev: node.prev}
			node.prev.next = n
			node.prev = n
		}
	}
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 {
		return
	}
	n, _ := this.getNode(index)
	if n == nil {
		return
	}
	if n.next != nil {
		n.next.prev = n.prev
	}
	if n.prev != nil {
		n.prev.next = n.next
	}
	if n == this.head {
		this.head = n.next
	}
	if n == this.tail {
		this.tail = n.prev
	}
}

sample 6900 KB submission

type LinkedListNode struct {
	val  int
	next *LinkedListNode
}

type MyLinkedList struct {
	head *LinkedListNode
	// tail   *LinkedListNode
	length int
}

func Constructor() MyLinkedList {
	return MyLinkedList{}
}

func (this *MyLinkedList) Get(index int) int {
	i := 0
	cur := this.head
	for cur != nil && i <= index {
		if i == index {
			return cur.val
		}
		cur = cur.next
		i++
	}
	return -1
}

func (this *MyLinkedList) AddAtHead(val int) {
	this.length++
	if this.head == nil {
		this.head = &LinkedListNode{val: val}
		// this.tail = this.head
		return
	}
	cur := this.head
	this.head = &LinkedListNode{val: val}
	this.head.next = cur
}

func (this *MyLinkedList) AddAtTail(val int) {
	this.AddAtIndex(this.length, val)
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index > this.length {
		return
	}
	if index == 0 {
		this.AddAtHead(val)
		return
	}
	this.length++
	i := 0
	cur := this.head
	for cur != nil && i <= index {
		if i == index-1 {
			curNext := cur.next
			cur.next = &LinkedListNode{val: val, next: curNext}
		}
		cur = cur.next
		i++
	}
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index == 0 {
		this.deleteAtHead()
		return
	}
	i := 0
	cur := this.head
	for cur != nil && i <= index {
		if i == index-1 {
			if cur.next != nil {
				curForward := cur.next.next
				cur.next = curForward
				this.length--
				break
			}
			cur.next = nil
			break
		}
		cur = cur.next
		i++
	}
}

func (this *MyLinkedList) deleteAtHead() {
	if this.head == nil {
		return
	}
	headNext := this.head.next
	this.head = headNext
	this.length--
	return
}

sample 7100 KB submission

type Node struct {
    prev, next *Node
    val int
}

type MyLinkedList struct {
    size int
    head, tail *Node
}

func Constructor() MyLinkedList {
    node1 := &Node{}
    node2 := &Node{prev: node1, next:nil}
    node1.next = node2    
    return MyLinkedList{
        head: node1,
        tail: node2,
        size: 0,
    }
}


func (this *MyLinkedList) Get(index int) int {
    if index < 0 || index >= this.size {
        return -1
    }
    return this.findByIndex(index).val
}


func (this *MyLinkedList) AddAtHead(val int)  {
    this.AddAtIndex(0, val)
}


func (this *MyLinkedList) AddAtTail(val int)  {
    this.AddAtIndex(this.size, val)
}


func (this *MyLinkedList) AddAtIndex(index int, val int)  {
    if index > this.size || index < 0 {
        return 
    }
    node := &Node{val: val}
    pt := this.findByIndex(index)
    prevNode := pt.prev
    prevNode.next = node
    pt.prev = node
    node.next = pt
    node.prev = prevNode
    this.size++
}


func (this *MyLinkedList) DeleteAtIndex(index int)  {
    if index < 0 || index >= this.size{
        return
    }
    pt := this.findByIndex(index)
    pt.prev.next = pt.next
    pt.next.prev = pt.prev
    this.size--
}

// assume index always smaller than/equals to this.size
func (this *MyLinkedList) findByIndex(index int) *Node {
    if index == this.size {
        return this.tail
    }
    
    pt := this.head.next
    for index > 0 {
        pt = pt.next
        index--
    }
    return pt
}

sample 7200 KB submission

type (
    NodeList struct {
        val int
        prev, next *NodeList
    }
    
    MyLinkedList struct {
        head, tail *NodeList
        length int
    }
)


func Constructor() MyLinkedList {
    return MyLinkedList{}
}


func (m *MyLinkedList) Get(index int) int {
    if index >= m.length {
        return -1
    }
    
    return m.getByIndex(index).val
}

func (m *MyLinkedList) getByIndex(index int) *NodeList {    
    if index >= m.length || m.length == 0 {
        return nil
    }
    
    if index == 0 {
        return m.head
    }
    
    if index == m.length - 1 {
        return m.tail
    }
    
    var cur *NodeList
    switch m.length / index > 2 {
    case true:
        cur = m.head
        for i := 0; i < index; i++ {
            cur = cur.next
        }
    case false:
        cur = m.tail
        for i := 0; i < m.length - index - 1; i++ {
            cur = cur.prev
        }
    }
    
    return cur
}

func (m *MyLinkedList) AddAtHead(val int) {
    newNode := NodeList{
        val: val,
        next: m.head,
    }
    
    if m.length == 0 {
        m.head = &newNode
        m.tail = &newNode
        m.length++
        return
    }
    
    m.head.prev = &newNode
    m.head = &newNode
    m.length++
}


func (m *MyLinkedList) AddAtTail(val int) {
    if m.length == 0 {
        m.AddAtHead(val)
        return
    }
    
    newNode := NodeList{
        val: val,
        prev: m.tail,
    }
    m.tail.next = &newNode
    m.tail = &newNode
    m.length++
}


func (m *MyLinkedList) AddAtIndex(index int, val int) {    
    if index > m.length {
        return
    }
    
    if index == 0 {
        m.AddAtHead(val)
        return
    }
    
    if index > m.length - 1 {
        m.AddAtTail(val)
        return
    }
    
    cur := m.getByIndex(index-1)
    newNode := NodeList{
        val: val,
        prev: cur,
        next: cur.next,
    }
    
    if cur.next != nil {
        cur.next.prev = &newNode
    }
    
    cur.next = &newNode
    m.length++
}


func (m *MyLinkedList) DeleteAtIndex(index int) {
    if index >= m.length || m.length == 0 {
        return
    }
    
    cur := m.getByIndex(index)
    if cur == nil {
        return
    }
    
    if cur.next != nil {
        cur.next.prev = cur.prev
    }
    
    if cur.prev != nil {
        cur.prev.next = cur.next
    }
    
    if index == 0 {
        m.head = m.head.next
    }
    
    if index == m.length - 1 {
        m.tail = m.tail.prev
    }
    
    m.length--
}