Python数据结构与算法(三)–单向链表、双向链表、单向循环链表

587-王同学

发表文章数:79

热门标签

, ,
首页 » 数据结构 » 正文

链表

结构

  • 一个节点分为两部分

    数据区

    链接区:

    指向下一个结点的地址

单向链表

链的方向只有一个

链表顺序表对比:

Python数据结构与算法(三)--单向链表、双向链表、单向循环链表

#单链表
class node(object):
    def __init__(self, ele):
        self.ele = ele
        self.next = None

class linklist(object):
    def __init__(self, node = None):
        self.__head = node
        #私有变量双下划线

    def is_empty(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
        print('travel_result = ')
        while cur != None:
            print(cur.ele)
            cur = cur.next

    def add(self, other):
        other_node = node(other)
        other_node.next = self.__head
        self.__head = other_node

    def append(self, other):
        cur = self.__head
        other_node = node(other)
        if self.is_empty():
            self.__head = other_node
        else:
            while cur.next != None:
                cur = cur.next
            cur.next = other_node

    def insert(self, pos, other):#pos从0开始
        other_node  = node(other)
        count = 0
        cur = self.__head
        if pos == 0:
            self.add(other)
        elif pos >= self.length() - 1:
            self.append(other)
        else:
            while count != pos - 1:
                count += 1
                cur = cur.next
            other_node.next = cur.next
            cur.next = other_node

    def remove(self, item):
        cur = self.__head
        pre = None
        while cur != None:
            if cur.ele == item:
                if cur == self.__head:
                    self.__head = cur.next
                    return True
                else:
                    pre.next = cur.next
                    return True
            else:
                pre = cur
                cur = cur.next

    def search(self, item):
        cur = self.__head
        count = 0
        while cur.ele != item:
            cur = cur.next
            count += 1
        return count


if __name__ == '__main__':
    ll = linklist()
    print(ll.is_empty())
    print(ll.length())
    ll.append(1)
    ll.append(5)
    ll.add(9)
    ll.insert(4, 7)
    ll.remove(9)
    ll.travel()
    print('length = ', ll.length())
    # print(ll.search(7))

双向链表

  • 结构

前驱节点

后继节点

数据区

#双向链表


class node(object):
    def __init__(self, item):
        self.ele = item
        self.prev = None
        self.next = None
class double_link_list(object):
    def __init__(self, node=None):
        self.__head = node
        # 私有变量双下划线

    def is_empty(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
        print('travel_result = ')
        while cur != None:
            print(cur.ele)
            cur = cur.next

    def add(self, other):
        other_node = node(other)
        other_node.next = self.__head
        self.__head = other_node
        other_node.next.prev = other_node

    def append(self, other):
        cur = self.__head
        other_node = node(other)
        if self.is_empty():
            self.__head = other_node
        else:
            while cur.next != None:
                cur = cur.next
            cur.next = other_node
            other_node.prev = cur

    def insert(self, pos, other):  # pos从0开始
        other_node = node(other)
        count = 0
        cur = self.__head
        if pos == 0:
            self.add(other)
        elif pos >= self.length() - 1:
            self.append(other)
        else:
            while count != pos - 1:
                count += 1
                cur = cur.next
            other_node.next = cur.next
            other_node.prev = cur.prev
            other_node.prev.next = other_node
            cur.prev = other_node


    def remove(self, item):
        cur = self.__head
        while cur != None:
            if cur.ele == item:
                if cur == self.__head:
                    self.__head = cur.next
                    if cur.next:#判断链表是否只有一个节点
                        cur.next.prev = None
                    return True
                else:
                    cur.prev.next = cur.next
                    if cur.next:
                        cur.next.prev = cur.prev
                    return True
            else:
                pre = cur
                cur = cur.next
        return False


    def search(self, item):
        cur = self.__head
        count = 0
        while cur.ele != item:
            cur = cur.next
            count += 1
        return count
if __name__ == '__main__':
    ll = double_link_list()
    print(ll.is_empty())
    print(ll.length())
    ll.append(1)
    ll.append(5)
    ll.add(9)
    ll.insert(4, 7)
    ll.remove(9)
    ll.travel()
    print('length = ', ll.length())
    # print(ll.search(7))

单向循环链表

尾节点指向头节点

#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: Caramel
@file: 3.2.py
@time: 2020/02/09
@desc:单向循环链表
"""
class node(object):
    def __init__(self, ele):
        self.ele = ele
        self.next = None

class single_cycle_linklist(object):
    def __init__(self, node = None):
        self.__head = node
        if node:
            node.next = node
        #私有变量双下划线

    def is_empty(self):
        return self.__head == None

    def length(self):
        cur = self.__head
        if self.is_empty():
            count = 0
            return count
        count = 1
        #单项循环链表从一开始
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        cur = self.__head
        if self.is_empty():
            return 0
        print('travel_result = ')
        while cur.next != self.__head:
            print(cur.ele)
            cur = cur.next
            #尾节点元素未被打印
        print(cur.ele)

    def add(self, item):
        """链表头部添加元素,头插法"""
        other_node = node(item)
        if self.is_empty():
            self.__head = other_node
            other_node.next = other_node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            # 退出循环,cur指向尾节点
            other_node.next = self.__head
            self.__head = other_node
            # cur.next = node
            cur.next = self.__head

    def append(self, other):
        cur = self.__head
        other_node = node(other)
        if self.is_empty():
            self.__head = other_node
            other_node.next = other_node
        else:
            while cur.next != self.__head:
                cur = cur.next
            cur.next = other_node
            other_node.next = self.__head

    def insert(self, pos, other):#pos从0开始
        other_node  = node(other)
        count = 0
        cur = self.__head
        if pos == 0:
            self.add(other)
        elif pos >= self.length() - 1:
            self.append(other)
        else:
            while count != pos - 1:
                count += 1
                cur = cur.next
            other_node.next = cur.next
            cur.next = other_node

    def remove(self, item):
        cur = self.__head
        pre = None
        if self.is_empty():
            return
        else:
            while cur.next != self.__head:
                if cur.ele == item:
                    if cur == self.__head:
                        self.__head = cur.next
                        cur_last = self.__head
                        while cur_last.next != cur:
                            cur_last = cur_last.next
                        cur_last.next = self.__head

                    else:
                        pre.next = cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
        #cur指向尾节点
            if cur.ele == item:
                if cur == self.__head:#链表中只有一个节点
                    self.__head = None
                else:
                    pre.next = cur.next

    def search(self, item):
        cur = self.__head
        count = 0
        while cur.ele != item:
            cur = cur.next
            count += 1
            if cur == self.__head:
                    return -1
            return count


if __name__ == '__main__':
    ll = single_cycle_linklist()
    print(ll.is_empty())
    print(ll.length())
    ll.append(1)
    ll.append(5)
    ll.add(9)
    ll.insert(4, 7)

    ll.remove(9)
    ll.travel()
    print('length = ', ll.length())
    # print(ll.search(7))

 

拜师教育学员文章:作者:587-王同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Python数据结构与算法(三)–单向链表、双向链表、单向循环链表》 发布于2020-02-09

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录