数据结构和算法，单链表的实现(kotlin版)

数据结构和算法，单链表的实现(kotlin版)

b站视频链接

单链表的实现–koltin版本

1.定义接口，我们需要实现的方法

interface LinkedListAction<E> {
    fun push(e: E)
    fun size(): Int
    fun getValue(index: Int): E?
    fun insert(index: Int,e: E)
    fun remove(index: Int)
}
1
2
3
4
5
6
7

2.定义节点，表示每个链表节点。

data class Node<E>(var next: Node<E>? = null, var value: E)
1

3.push(e: E)，链表尾部新增一个节点

override fun push(e: E) {
        val newNode = Node(null, e)
        if (head != null) {
//            val lastNode = node(len - 1)
            //O（1）时间复杂度
            last?.next = newNode
        } else {
            head = newNode
        }
        last = newNode
        len++
    }
1
2
3
4
5
6
7
8
9
10
11
12

4.size(): Int，返回链表的长度

override fun size(): Int {
        return len
    }
1
2
3

5.getValue(index: Int): E?，获取列表的value值

    override fun getValue(index: Int): E? {
        if (index < 0 || index >= len) {
            throw ArrayIndexOutOfBoundsException("数组越界.....")
        }
        return node(index)?.value
    }
	//找到对应index下标的节点。
    private fun node(index: Int): Node<E>? {
        var h = head
        //O（n）时间复杂度
        for (i in 0 until index) {
            h = h?.next
        }
        return h
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6.insert(index: Int,e: E)，从任意位置插入一个节点

override fun insert(index: Int, e: E) {
        val newNode = Node(null, e)
        //考虑边界
        if (index == 0) {
            val h = head
            head = newNode
            newNode.next = h
        } else {
            //考虑最后一个位置
            val prev = node(index - 1)
            val next = prev?.next
            prev?.next = newNode
            newNode.next = next
        }
        len++
    }
    //找到对应index下标的节点。
    private fun node(index: Int): Node<E>? {
        var h = head
        //O（n）时间复杂度
        for (i in 0 until index) {
            h = h?.next
        }
        return h
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

7.remove(index: Int)，任意位置删除一个节点

override fun remove(index: Int) {
        if (index < 0 || index >= len) {
            throw ArrayIndexOutOfBoundsException("数组越界.....")
        }
        if (index == 0) {
            val h = head
            head = h?.next
            h?.next = null
        } else {
            val prev = node(index - 1)
            val current = prev?.next
            prev?.next = current?.next
            current?.next = null
        }
        len--
    }
    //找到对应index下标的节点。
    private fun node(index: Int): Node<E>? {
        var h = head
        //O（n）时间复杂度
        for (i in 0 until index) {
            h = h?.next
        }
        return h
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

8.完整Demo

package day1

class LinkedList<E> : LinkedListAction<E> {
    //头指针
    private var head: Node<E>? = null
    //优化时间复杂度
    private var last: Node<E>? = null
    //集合的长度
    private var len = 0
    override fun push(e: E) {
        val newNode = Node(null, e)
        if (head != null) {
//            val lastNode = node(len - 1)
            //O（1）时间复杂度
            last?.next = newNode
        } else {
            head = newNode
        }
        last = newNode
        len++
    }

    //找到对应index下标的节点。
    private fun node(index: Int): Node<E>? {
        var h = head
        //O（n）时间复杂度
        for (i in 0 until index) {
            h = h?.next
        }
        return h
    }

    override fun size(): Int {
        return len
    }

    override fun getValue(index: Int): E? {
        if (index < 0 || index >= len) {
            throw ArrayIndexOutOfBoundsException("数组越界.....")
        }
        return node(index)?.value
    }

    override fun insert(index: Int, e: E) {
        val newNode = Node(null, e)
        //考虑边界
        if (index == 0) {
            val h = head
            head = newNode
            newNode.next = h
        } else {
            //考虑最后一个位置
            val prev = node(index - 1)
            val next = prev?.next
            prev?.next = newNode
            newNode.next = next
        }
        len++
    }

    override fun remove(index: Int) {
        if (index < 0 || index >= len) {
            throw ArrayIndexOutOfBoundsException("数组越界.....")
        }
        if (index == 0) {
            val h = head
            head = h?.next
            h?.next = null
        } else {
            val prev = node(index - 1)
            val current = prev?.next
            prev?.next = current?.next
            current?.next = null
        }
        len--
    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79