数据结构与算法学习日记（1）-- 链表1

1. 链表结构

与数组相似，链表也是一种线性数据结构。

链表有两种类型：单链表和双链表

本文只讲述单链表。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

2.  链表创建

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class ListLink(object):
    def __init__(self, head=None):
        self.head = head

    def initlink(self, ListNums):
        if not ListNums:
            return
        head = ListNode(0)
        prehead = head
        for num in ListNums:
            head.next = ListNode(num)
            head = head.next
        self.head = prehead.next

    def link2list(self):
        ListNums = []
        node = self.head
        while node:
            ListNums.append(node.val)
            node = node.next
        return ListNums

ListNums = [24, 33, 21, 1, 76, 45, 61]
link = ListLink()
link.initlink(ListNums)
print(link.link2list())

[24, 33, 21, 1, 76, 45, 61]

不在ListNode类中写类方法，是因为如果要删除只有一个节点的链表，就需要将链表对象置为None，对象无法调用成员函数将自身置为None（不知道怎么实现）。

3. 插入节点

class ListLink(object):
    def __init__(self, head=None):
        self.head = head

    def insertNode(self, num, index="end"):
        node = ListNode(num)

        # 在表头插入
        if index == 0:
            self.head, node.next = node, self.head
            return

        # 在[1:len-1)范围插入
        curnode = self.head
        i = 1
        while True:
            if index == i:
                curnode.next, node.next = node, curnode.next
                return
            i += 1
            if not curnode.next:
                break
            curnode = curnode.next

        # 在表尾插入
        if index == "end":
            curnode.next = node

ListNums = [24, 33, 21, 1, 76, 45, 61]
head = ListNode().list2link(ListNums)

• 表头插入