链表

2018年04月30日

单链表

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

    def __str__(self):
        return str(self.data)

    def delete(self):
        self.data = None
        self.next = None

class LNode:
    def __init__(self, has_head=True):
        self.node = None
        if has_head:
            self.head = None
        self.length = 0
    
    def if_has_head(self):
        if hasattr(self, 'head'):
            return True
        else:
            return False

    def is_empty(self):
        if self.length == 0:
            return True
        return False

    def append(self, data):
        current = self.node
        if self.is_empty():
            self.node = Node(data)
        else:
            while current.next:
                current = current.next
            current.next = Node(data)
        self.length += 1
        
    def insert(self, pos, data):
        if pos > self.length + 1 or pos <=0:
            return False
        if pos == 1:
            self.push(data)
        else:
            current = self.node
            for i in range(pos-2):
                current = current.next
            temp = current.next
            current.next = Node(data,temp)
            self.length += 1
        return True

    def push(self, data):
        temp = self.node
        self.node = Node(data,temp)
        self.length += 1

    def pop(self):
        last = self.node
        for i in range(self.length-2):
            last = last.next
        data = last.next.data
        last.next.delete()
        last.next = None
        self.length -= 1
        return data

    def remove(self, pos):
        if pos > self.length or pos <= 0:
            return False
        else:
            if pos == 1:
                next = self.node.next
                self.node.delete()
                self.node = next
            else:
                last = self.node
                for i in range(pos-2):
                    last = last.next
                current = last.next
                next = current.next
                last.next = next
                current.delete()
            self.length -= 1
            return True

    def get_node(self, pos):
        if pos > self.length or pos <= 0:
            return None

        current = self.node
        for i in range(pos-1):
            current = current.next
        return current.data

    def find_node(self, data):
        current = self.node
        pos = 1
        while current:
            if current.data == data:
                return pos
            else:
                pos += 1
                current = current.next
        return -1 

    def get_lnode(self):
        current = self.node
        result = []
        while current:
            result.append(current.data)
            current = current.next
        return result

    def clear(self):
        if self.if_has_head:
            self.head = None
        current = self.node
        self.node = None
        while current:
            temp = current.next
            current.next = None
            current.delete()
            current = temp
        self.length = 0

    def __len__(self):
        return self.length

单链表的反转

算法

阅读全文