链表及Python实现

本文介绍链表的基本概念以及使用Python实现链表的基本功能，包括添加、删除、查找、更新节点等。

class Node(object):
    def __init__(self, data, pnext=None):
        """
        初始化
        """
        self.data = data
        self._next = pnext
        
    def __repr__(self):
        return str(self.data)

class ChainTable(object):
    def __init__(self):
        self.head = None
        self.length = 0
        
    def isEmptyp(self):
        return self.length==0
    
    def append(self, dataOrNode):
        # 增加节点，将数据或者节点类型转化为节点类型
        item = None
        if isinstance(dataOrNode, Node):
            item = dataOrNode
        else:
            item = Node(dataOrNode)
        
        # 判断根节点是否为空，为空时，从根结点开始
        if not self.head:
            self.head = item
            self.length += 1
        # 根节点不为空，从根节点开始遍历，直到节点的指针为空
        else:
            node = self.head
            while node._next:
                node = node._next
            node._next = item
            self.length += 1
            
    def delete(self, index):
        if self.isEmptyp():
            print("This chain table is empty!")
            return
        if index < 0 or index >= self.length:
            print ("Error: out of index")
            return
        # 删除根节点
        if index == 0:
            self.head = self.head._next
            self.length -= 1
            return
        # 保存index-1的节点，跳过第index个的节点
        j = 0
        node = self.head
        prev = self.head
        while node._next and j < index:
            prev = node
            node = node._next
            j += 1
        if j == index:
            prev._next = node._next
            self.length -= 1
            
    def update(self, index, data):
        if self.isEmptyp() or index < 0 or index >= self.length:
            print("Error: out of index")
            return
        j = 0
        node = self.head
        while node._next and j < index:
            node = node._next
            j += 1
        if j == index:
            node.data = data
            
    def getItem(self, index):
        if self.isEmptyp() or index < 0 or index >= self.length:
            print("Error: out of index")
            return
        j = 0
        node = self.head
        while node._next and j < index:
            node = node._next
            j += 1
        return node.data
    
    def getIndex(self, data):
        if self.isEmptyp() or index < 0 or index >= self.length:
            print("Error: out of index")
            return
        node = self.head
        while node:
            if node.data == data:
                return j
            node = node._next
            j += 1
        if j == self.length:
            print("%s not found".format(data))
            return
        
    def insert(self, index, dataOrNode):
        if self.isEmptyp():
            print("This chain table is empty!")
            return
        if index < 0 or index >= self.length:
            print ("Error: out of index")
            return
        # 增加节点，将数据或者节点类型转化为节点类型
        item = None
        if isinstance(dataOrNode, Node):
            item = dataOrNode
        else:
            item = Node(dataOrNode)
            
        if index == 0:
            item._next = self.head
            self.head = item
            self.length += 1
            return
        j = 0
        node = self.head
        prev = self.head
        while node._next and j < index:
            prev = node
            node = node._next
            j += 1
        if j == index:
            item._next = node
            prev._next = item
            self.length += 1
    
    def clear(self):
        self.head = None
        self.length = 0
        
    def __repr__(self):
        """
        打印链表
        """
        if self.isEmptyp():
            return "Empty chain table"
        node = self.head
        nlist = ''
        while node:
            nlist += str(node.data)+' '
            node = node._next
        return nlist
    def __getitem__(self, ind):
        if self.isEmptyp() or ind < 0 or ind >= self.length:
            print("Error: out of index")
            return
        return self.getItem(ind)
    
    def __setitem__(self, ind, val):
        if self.isEmptyp() or ind < 0 or ind >= self.length:
            print("Error: out of index")
            return
        return self.update(ind, val)
    
    def __len__(self):
        return self.length

chain = ChainTable()
chain.append((10,2))
chain.append(5)
len(chain)
chain[0]

(10, 2)