python实现链表(单链表)

2022年 11月 4日

python实现链表(单链表)

python对链表的实现

什么是链表？

链表就是若干个节点连接起来组成的一条链子.每个节点存储着自己的数据的同时还记录着下一个节点的位置.
它可以是有序(各节点的数据是按照指定标准排序的)的,也可以是无序(各节点在链表中的顺序是插入时的顺序,没有刻意进行排序)的
由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间(因为只有通过前一个节点才能访问到当前节点).
一般链表具有插入节点,删除节点,查找节点数据的基本功能

用python实现链表(version 3.7.2)

首先要有Node(节点)对象

class Node:
    def __init__(self, initdata):
        self.data = initdata
        print(self.data)
        self.next = None
	# 获得节点中的数据
    def getData(self):
        return self.data
	# 获得当前节点记录的下一个节点
    def getNext(self):
        return self.next
	# 设置节点的数据
    def setData(self, newdata):
        self.data = newdata
	# 设置当前节点记录的下一个节点
    def setNext(self, newNext):
        self.next = newNext

然后是实现无序单链表

# 无序链表
import Node

class LinkedList:
    # 初始化链表头
    def __init__(self):
        self.head = None
        
    # 向链表中添加节点,这里是头插法(默认从头部插入节点)
    def add(self, item):
        temp = Node.Node(item)
        temp.setNext(self.head)
        self.head = temp

    # 获得链表当前的节点数
    def size(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()
        return count

    # 查找某一个值
    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

    # 删除某一个值所在的节点
    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found and current != None:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())

接下来是有序单链表

from Node import *

class OrderLinkedList:
    def __init__(self):
        self.head = None

	#和无序链表的区别在于插入时要对已存在的节点的数据进行比较,找到合适的位置进行插入
    def add(self, item):
        current = self.head
        stop = False
        previous = None
        while current != None and not stop:
            if current.getData() > item:
                stop = True
            else:
                previous = current
                current = current.getNext()
        temp = Node(item)
        if previous == None:
            temp.setNext(self.head)
            self.head = temp
        else:
            temp.setNext(current)
            previous.setNext(temp)

    def search(self, item):
        current = self.head
        found = False
        stop = False
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:
                    stop = True
                else:
                    current = current.getNext()
        return found

    def remove(self, item):
        current = self.head
        previous = None
        found = False
        stop = False
        while current != None and not found and not stop:
            if current.getData() == item:
                if previous == None:
                    self.head = current.getNext()
                else:
                    previous.setNext(current.getNext())
                return True
            else:
                if current.getData() > item:
                    return False
                else:
                    previous = current
                    current = current.getNext()
        return False

如有错误还望指出
允许转载但请注明出处