""" =============================== 链表的常规操作 ====================================== https://blog.csdn.net/Blood_Seeker/article/details/78992722 """


class ListNode(object):
    #结点初始化函数, p 即模拟所存放的下一个结点的地址
    #为了方便传参, 设置 p 的默认值为 0
    def __init__(self, x = None):
        self.val = x
        self.next = None

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

    #链表初始化函数, 方法类似于尾插
    def initList(self, dataList):
        #创建头结点
        self.head = ListNode(None) # 创建节点的时候传一个参数进去 # 创建头结点，里面不包含数据，头结点之后第一个才存放数据,head节点的数据默认None
        pTail = self.head              # 指向头结点的指针
        #逐个为 data 内的数据创建结点, 建立链表
        for i in dataList:            # 遍历列表
            newNode = ListNode(i)        # 生成新的节点
            pTail.next = newNode      # 新节点挂在尾结点上，即 上一个节点指针指向新的节点，由于新节点的next被初始化为None，所以pTail的next自然也是None
            pTail = newNode          # 当前新节点成为新的尾结点

    #链表判空
    def isEmpty(self):
        return self.head.next is None

    #取链表长度
    def getLength(self):
        if self.isEmpty():
            exit(0)

        p = self.head.next
        len = 0
        while p:
            len += 1
            p = p.next
        return len

    #遍历链表
    def traveList(self):
        if self.isEmpty():
            exit(0)
        print ('link list traving result:')
        p = self.head.next   # 取得表头之后的第一个数据
        while p:
            print (p.val, end= " ")
            p = p.next


    #链表插入数据函数
    def insertElem(self, val, index):
        """ 在 第index个节点(p.next)之前插入"""

        p = self.head
        i = 1
        while p and i < index:
            p = p.next
            i = i + 1
        if p is None or i > index:
            print("ERROR, 无法插入节点")
            return False
        pNew = ListNode(val)    # 生成新的节点 包含了 pNew.val = key
        pNew.next = p.next
        p.next = pNew


    def deleteElem(self, index):
        "删除第index个节点（即删除 p.next节点）"

        p = self.head
        i = 1             # 节点计数
        while p.next and i < index:
            p = p.next
            i = i + 1
        if p.next is None or i > index:
            print("ERROR, 该节点不存在")
            return False

        delVal = p.next.val
        print("deleted value:", delVal)
        p.next = p.next.next



if __name__ == '__main__':

    #初始化链表与数据
    # data = [1,2,3,4,5]
    dataList = [1, 2, 3, 4, 5]
    l = LinkList()
    l.initList(dataList)
    l.traveList()
    print('\n')

    print(l.getLength())

    #插入结点到索引值为3之后, 值为666
    l.insertElem(666, 6)
    l.traveList()
    print('\n')

    #删除索引值为4的结点
    l.deleteElem(4)
    l.traveList()
    print('\n')

参考：

  1. 链表操作