天天看点
返回

数据结构与算法 4.链表 LinkList

链表 LinkList 

定义：链表是由一系列节点组成的元素集合
每个节点node包含两部分：数据域item和指向下一节点的指针next，双向链表还有指向上一节点的指针prev
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
链表可以做到用多少空间就申请多少存储空间

分类：单链表，循环链表，双向链表

链表的接口设计：
    isEmpty()           判断链表是否为空
    length()            返回链表的长度
    travel()            遍历链表
    add(item)           在头部添加节点
    append(item)        在尾部添加节点
    insert(pos,item)    在指定位置添加节点
    remove(item)        删除节点
    search(item)        查找节点是否存在

链表 与 顺序表 同一操作的时间复杂度
    访问元素：n 1
    头部添加：1 n
    尾部添加：n 1
    中间添加：n n

单链表

定义单位元素 
class Node(object):
    def __init__(self,item):
        self.item = item
        self.next = None
定义单链表 
class LinkList(object):
    def __init__(self):
        self.head = None

    # 判断链表是否为空
    def isEmpty(self):
        return self.head == None

    # 获取链表长度，在遍历链表的过程中记录节点数量
    def length(self):
        cur = self.head

        count = 0
        while cur != None :
            count += 1
            cur = cur.next
        return count

    # 遍历链表
    def travel(self):
        cur = self.head
        while cur :
            print(cur.item)
            cur = cur.next
        return None

    # 在链表头部添加节点
    def addFirst(self,item):
        node = Node(item)
        # 无论链表是否为空
        node.next = self.head
        self.head = node

    # 在链表尾部添加节点
    def append(self,item):
        node = Node(item)

        cur = self.head
        # 如果链表为空，添加的节点既是首节点也是尾节点
        if self.isEmpty():
            self.head = node
        # 链表不为空，先遍历，再添加
        else :
            cur = self.head
            while cur.next :
                cur = cur.next
            cur.next = node

    # 在链表指定位置添加节点
    def insert(self,pos,item):
        # 添加的位置小于1，调用添加首节点的方法
        if pos <= 0 :
            self.addFirst(item)
        # 添加的位置大于链表长度-1，调用添加尾节点的方法
        elif pos > (self.length() - 1) :
            self.append(item)
        # 插入到链表中间位置，使用count记录指针移动的位置
        else :
            node = Node(item)
            count = 0
            pre = self.head
            # 移动到插入位置前面时，循环结束
            while count < (pos - 1) :
                count += 1
                pre = pre.next
            node.next = pre.next
            pre.next = node

    # 删除节点
    def remove(self,item):
        # 创建副指针pre，始终在主指针cur后面一个位置
        cur = self.head
        pre = None
        # 遍历链表，直至找到要删除的节点
        while cur != None :
            # 当前节点是要删除的节点
            if cur.item == item :
                # 要删除的节点是首节点，直接设置为None
                if not pre :
                    self.head = cur.next
                # 把被删除节点的前后两个节点相连
                else :
                    pre.next = cur.next
                break
            # 当前节点不是要删除的节点，分别移动两个指针
            else :
                pre = cur
                cur = cur.next

    # 查找节点是否存在
    def search(self,item):
        cur = self.head
        # 遍历链表，逐一对比元素的值
        while cur != None :
            if cur.item == item :
                return True
            cur = cur.next
        return False

单向循环链表

定义单位元素 
class Node(object):
    def __init__(self,item):
        self.item = item
        self.next = None
定义循环链表 
class CirLinkList(object):
    def __init__(self):
        self.head = None

    # 判断链表是否为空
    def isEmpty(self):
        return self.head == None

    # 获取链表长度
    def length(self):
        if self.isEmpty() :
            return 0

        count = 1
        cur = self.head
        while cur.next != self.head :
            count += 1
            cur = cur.next
        return count

    # 遍历链表
    def travel(self):
        if self.isEmpty() :
            return

        cur = self.head
        print(cur.item)
        while cur.next != self.head :
            cur = cur.next
            print(cur.item)

    # 在链表头部添加节点
    def addFirst(self,item):
        node = Node(item)

        # 链表为空则添加的节点就是首节点
        if self.isEmpty() :
            self.head = node
            node.next = self.head
        # 链表不为空，先把节点连接到首节点，再把尾节点的.next从原首节点换到新节点
        else:
            node.next = self.head
            cur = self.head
            while cur.next != self.head :
                cur = cur.next
            cur.next = node
            self.head = node

    # 在链表尾部添加节点
    def append(self,item):
        node = Node(item)

        # 链表为空则添加的节点就是尾节点
        if self.isEmpty() :
            self.head = node
            node.next = self.head
        # 链表不为空，先把尾节点的.next从原首节点换到新节点，再把新节点与首节点相连
        else:
            cur = self.head
            while cur.next != self.head :
                cur = cur.next
            cur.next = node
            node.next = self.head

    # 在指定位置添加节点
    def insert(self,pos,item):
        # 添加位置小于1，调用添加首节点的方法
        if pos <= 0 :
            self.addFirst(item)
        # 添加位置大于链表长度-1，调用添加尾节点的方法
        elif pos > (self.length() - 1) :
            self.append(item)
        # 插入到链表中间位置，用ind记录指针移动的位置，在添加位置的前一个节点停下，先连接，再断开
        else:
            node = Node(item)
            cur = self.head
            ind = 0
            while ind < (pos - 1) :
                ind += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    # 删除节点
    def remove(self,item):
        if self.isEmpty() :
            return

        cur = self.head
        # 判断要删除的节点是否为首节点
        if cur.item == item :
            # 删除首节点，判断链表是否只有一个节点
            if cur.next != self.head :
                # 有多个节点，把尾节点与第二个节点相连，再把第二个节点设为首节点
                while cur.next != self.head :
                    cur = cur.next
                cur.next = self.head.next
                self.head = self.head.next
            # 只有一个节点，直接删除
            else:
                self.head = None
        # 要删除的节点不是首节点
        # 再创建一个指针副pre，始终在主指针cur后面一个位置
        else :
            pre = self.head
            while cur.next != self.head :
                pre = cur
                cur = cur.next
                # cur到达要删除节点的位置时，连接前后两个节点
                if cur.item == item :
                    pre.next = cur.next
                    return

    # 搜索节点是否存在
    def search(self,item):
        if self.isEmpty() :
            return False

        # 判断搜索的元素是否在首节点
        cur = self.head
        if cur.item == item :
            return True
        # 在遍历过程中逐一对比
        while cur.next != self.head :
            cur = cur.next
            if cur.item == item :
                return True
        return False

双向链表

定义单位元素 
class Node(object):
    def __init__(self,item):
        self.item = item
        self.next = None
        self.prev = None
定义双向链表 
class DouLinkList(object):
    def __init__(self):
        self.head = None

    # 判断链表是否为空
    def isEmpty(self):
        return self.head == None

    # 获取链表长度
    def length(self):
        if self.isEmpty() :
            return 0

        count = 0
        cur = self.head
        while cur != None :
            count += 1
            cur = cur.next
        return count

    # 遍历链表
    def travel(self):
        if self.isEmpty():
            return

        cur = self.head
        while cur != None :
            print(cur.item)
            cur = cur.next

    # 在链表头部添加节点
    def addFirst(self,item):
        node = Node(item)

        if self.isEmpty() :
            self.head = node
        else :
            # 先建立连接，再修改节点的值
            node.next = self.head
            self.head.prev = node
            self.head = node

    # 在链表尾部添加节点
    def append(self,item):
        node = Node(item)

        if self.isEmpty() :
            self.head = node
        else :
            # 遍历链表直到尾节点，然后设置.next和.prev，使两个节点相连
            cur = self.head
            while cur.next != None :
                cur = cur.next
            cur.next = node
            node.prev = cur

    # 在指定位置添加节点
    def insert(self,pos,item):
        # 添加位置小于1，调用添加首节点的方法
        if pos <= 0 :
            self.addFirst(item)
        # 添加位置大于链表长度-1，调用添加尾节点的方法
        elif pos > (self.length() - 1) :
            self.append(item)
        # 添加到链表中间位置
        else :
            # 使用ind记录指针移动的位置
            node = Node(item)
            cur = self.head
            ind = 0
            # 到达添加位置前面时循环结束
            while ind < (pos - 1) :
                ind += 1
                cur = cur.next
            # 先连接，后断开
            node.next = cur.next
            node.prev = cur
            cur.next.prev = node
            cur.next = node

    # 删除节点，把被删除节点的前后两个节点互相连接，即完成删除
    def remove(self,item):
        if self.isEmpty() :
            return

        cur = self.head
        # 要删除的节点是首节点，则判断链表长度
        if cur.item == item :
            # 链表只有一个节点，直接删除
            if cur.next == None :
                self.head = None
            # 链表有多个节点，把第二个节点设为首节点
            else :
                cur.next.prev = None
                self.head = cur.next
            return
        # 要删除的节点不是首节点
        else :
            while cur != None :
                # 找到要删除的节点时，先将其前一个节点的.next指向其后一个节点
                if cur.item == item:
                    # 再判断要删除的是否为尾节点，是则直接删除
                    cur.prev.next = cur.next
                    if cur.next == None :
                        cur = None
                        return
                    # 不是则将其后一个节点的.prev指向其前一个节点
                    else :
                        cur.next.prev = cur.prev
                cur = cur.next

    # 搜索节点是否存在于链表
    def search(self,item):
        if self.isEmpty() :
            return False
        
        # 遍历链表，逐一判断元素值
        cur = self.head
        while cur != None :
            if cur.item == item :
                return True
            else :
                cur = cur.next
        return False
链表 添加节点 删除节点 双向链表 指定位置
上一篇: 数据结构与算法 5.树
下一篇: 数据结构与算法 3.队列 Queue

继续阅读