基本数据结构-python实现

SingleLinkList.py

class SingleNode:
    def __init__(self, item):
        self.item = item
        self.next = None
    
class SingleLinkList:
    def __init__(self):
        self._head = None

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

    def length(self):
        current = self._head
        count = 0
        while current != None:
            count += 1
            current = current.next
        return count

    def travel(self):
        current = self._head
        while current != None:
            print(current.item)
            current = current.next
        print("")

    def add(self, item):
        node = SingleNode(item)
        node.next = self._head
        self._head = node 

    def append(self, item):
        node = SingleNode(item)
        if self.is_empty():
            self._head = node
        else:
            current = self._head
            while current.next != None:
                current = current.next
            current.next = node

    def insert(self, pos, item):
        if pos <=0:
            self.add(item)
        elif pos >(self.length() -1):
            self.append(item)
                    
        else:            
            node = SingleNode(item)
            count = 0
            pre = self._head
            while count < (pos-1):
                count += 1
                pre = pre.next
            node.next = pre.next
            pre.next = node
            
    def search(self,item):
        current = self._head
        while current != None:
            if current.item == item:
                return True
            current = current.next
        return False

    def remove(self, item):
        current = self._head
        pre = None
        while current != None:
            if current.item == item:
                if not pre:
                    self._head = current.next
                else:
                    pre.next = current.next
                break
            else:
                pre = current
                current = current.next

    

if __name__ == "__main__":
    ll = SingleLinkList()
    ll.add(1)
    ll.add(2)
    ll.append(3)
    ll.insert(2, 4)
    print("length:",ll.length())
    ll.travel()
    print(ll.search(3))
    print(ll.search(5))
    ll.remove(1)
    print("length:",ll.length())
    ll.travel()

list_stack.py

class Stack(object):
    """栈"""
    def __init__(self):
        self.items = []


    def is_empty(self):
        """判断是否为空"""
        return self.items == []

    def push(self, item):
        """加入元素"""
        self.items.append(item)

    def pop(self):
        """弹出元素"""
        self.items.pop()

    def peek(self):
        """返回栈顶元素"""
        return self.items[len(self.items) - 1]

    def size(self):
        """返回栈的大小"""
        return len(self.items)

if __name__ == "__main__":

    def test():
        print(stack.size())
        print(stack.peek())
        stack.pop()
        
    stack = Stack()
    stack.push("hello")
    stack.push("world")
    stack.push("itcast")
    test()
    test()
    test()

list_queue.py

class Queue(object):
    """队列"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []


    def enqueue(self, item):
        return self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()


    def size(self):
        return len(self.items)




if __name__ == "__main__":
    def test():
        print(q.size())
        print(q.dequeue())
    q = Queue()
    q.enqueue("hello")
    q.enqueue("world")
    q.enqueue("itcast")
    test()
    test()
    test()

list_Deque.py

class Deque(object):
    """双端队列"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        """判断队列是否为空"""
        return self.items == []

    def add_front(self, item):
        """在队头添加元素"""
        return self.items.insert(0, item)


    def add_rear(self, item):
        """在队尾添加元素"""
        return self.items.append(item)

    def remove_front(self):
        """从队头删除元素"""
        return self.items.pop(0)


    def remove_rear(self):
        """从队尾删除元素"""
        return self.items.pop()


    def size(self):
        """返回队列大小"""  
        return len(self.items)



if __name__ == "__main__":

    deque = Deque()
    print(deque.size())
    print(deque.is_empty())
    deque.add_front(1)
    deque.add_front(2)
    deque.add_rear(3)
    deque.add_rear(4)
    print(deque.size())

    deque.remove_front()
    print(deque.items)
    deque.remove_rear()
    print(deque.items)