python3实现单向链表

python3实现单向链表

最近重学数据结构，无奈c语言已经忘得一干二净，所以干脆用python来写。

一、代码结构：

• 节点类

• 单向列表类

  • 链表初始化操作

    • init 　　初始化链表

      • is_empty　　判断链表是否为空

      • get_len　　 获取链表的长度

      • clear_list　　清除列表

    • 增加节点

      • append　　 从链表尾部添加节点

      • insert　　 在链表的任意位置插入节点

    • 删除节点

      • remove　　 删除节点内容 为data的所有节点

      • pop　　　　 删除第i个节点并且返回节点的内容

      • 查看节点

      • get_data 查看第i个节点的内容

二、代码详情

#-*- coding:utf-8 -*-
#Author: Bing Xu

class Node(object):
    def __init__(self,data):
        self.data = data
        self.next = None

class Single_Linklist(object):
    def __init__(self):
        '''
        链表初始化
        '''
        self.head_node = None

    def is_empty(self):
        '''
        判断链表是否为空
        :return:
        '''
        return self.head_node == None

    def get_len(self):
        '''
        获取链表对象的长度
        :return: 链表长度
        '''
        counter = 0
        cur = self.head_node
        while cur:
            counter += 1
            cur = cur.next
        return counter

    def clear_list(self):
        '''
        清除链表所有元素
        :return: 空链表
        '''
        self.head_node = None

    def append(self,data):
        '''
        链表尾部追加节点
        :param data: 追加节点的内容
        :return:
        '''
        node = Node(data)
        if self.is_empty():
            self.head_node = node
        else:
            cur = self.head_node
            while cur.next:
                cur = cur.next
            cur.next = node

    def insert(self,i,data):
        '''
        插入新的节点
        :param i: 待插入的位置,0 <= i <= self.length
        :param data: 待插入的节点数据
        :return:
        '''
        node = Node(data)
        length = self.get_len()
        cur = self.head_node
        if length >= i:
            if i == 0:
                self.head_node = node
                node.next = cur
            else:
                for item in range(i-1):
                    cur = cur.next
                temp = cur.next
                cur.next = node
                node.next = temp
        else:
            return False

    def remove(self,data):
        '''
        删除链表内容为data的所有节点
        :param data: 要删除的内容
        :return:
        '''
        cur = self.head_node
        if cur.data == data:
            self.head_node = cur.next
            return
        else:
            while cur.next:
                # temp = cur
                # cur = cur.next
                temp,cur = cur,cur.next
                if cur.data == data:
                    temp.next = cur.next

    def pop(self,i):
        '''
        删除链表对象第i个节点并返回该节点内容
        :param i: 要删除的节点,0 <= i < self.length
        :return: 删除节点的内容
        '''
        length = self.get_len()
        cur = self.head_node
        if i == 0:
            Data = cur.data
            self.head_node = cur.next
            return Data
        elif i < length:
            for j in range(i):
                temp, cur = cur, cur.next
            Data = cur.data
            temp.next = cur.next
            return Data

    def reset_data(self,i,data):
        '''
        修改第i个节点的内容
        :param i: 要修改的节点，0 <= i < self.length
        :param data: 修改后的内容
        :return:
        '''
        cur = self.head_node
        if 0 <= i < self.get_len():
            for j in range(i):
                cur = cur.next
            cur.data = data
        else:
            return False

    def get_data(self,i):
       '''
       获取链表第i个的值
       :param i: 0 <= i < self.length
       :return: 节点的内容
       '''
       cur = self.head_node
       if 0 <= i < self.get_len():
           for j in range(i):
               cur = cur.next
           return cur.data
       else:
           return False

三、代码测试

# 链表初始化：
sin_list = Single_Linklist()
print(sin_list.get_len())
print(type(sin_list))

# 结果为：
<class '__main__.Single_Linklist'>

# 增：
for i in range(10):
    sin_list.append(i)
sin_list.insert(0,'insert')

print(sin_list.get_len())
for j in range(sin_list.get_len()): #遍历打印
    print(sin_list.get_data(j),end=',')

# 结果：
insert,0,1,2,3,4,5,6,7,8,9,

# 删
for i in range(10):
    sin_list.append(i)

sin_list.remove(0)
sin_list.pop(sin_list.get_len()-1)

for j in range(sin_list.get_len()):  #遍历打印
    print(sin_list.get_data(j),end=',')

结果：
1,2,3,4,5,6,7,8,

# 改
for i in range(10):
    sin_list.append(i)

sin_list.reset_data(0,'修改')
sin_list.reset_data(9,'完成')

for j in range(sin_list.get_len()): #遍历打印
    print(sin_list.get_data(j),end=',')

结果：
修改,1,2,3,4,5,6,7,8,完成,