python 链表常见操作

淡淡的烟草味﹌ 2022-01-20 04:17 328阅读 0赞

# 链表 #

链表由一系列不必在内存中相连的结构构成，这些对象按线性顺序排序。每个结构含有表元素和指向后继元素的指针。最后一个单元的指针指向NULL。为了方便链表的删除与插入操作，可以为链表添加一个表头。

链表的基本元素有：
    
    	节点：每个节点有两个部分，左边部分称为值域，用来存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针。
    	head:head节点永远指向第一个节点
    	tail: tail永远指向最后一个节点
    	None:链表中最后一个节点的指针域为None值

## 单向链表属性及基本操作 ##

# 定义一个Node类
    class Node():
        def __init__(self, value = None, next = None):
            self._value = value
            self._next = next
    
        def get_value(self):
            return self._value
    
        def get_next(self):
            return self._next
    
        def set_value(self, new_value):
            self._value = new_value
    
        def set_next(self, new_next):
            self._next = new_next
     
     #实现Linked List及其各类操作方法      
    class LinkedList():
        def __init__(self):
            self._head = Node()
            self._tail = Node()
            self._length = 0
    
    	# 判断非空
        def is_empty(self):
            return self._head == None
    
        # add在链表前端添加元素
        def add(self, value):
            new_node = Node(value, None)
            new_node.set_next(self._head)
            self._head = new_node
    
    	# append在链表尾部添加元素
        def append(self, value):
            new_node = Node(value)
            if self.is_empty():
                self._head = new_node
            else:
                current = self._head
                while current.get_next() != None:
                    current = current.getNext()
                current.set_next(new_node)
    
        # search检索元素是否在链表中
        def search(self, value):
            current = self._head
            foundvalue = False
            while current != None and not foundvalue:
                if current.get_value() == value
                    foundvalue = True
                else:
                    current = current.get_next()
            return foundvalue
    
        # index索引元素在链表中的位置
        def index(self, value):
            current = self._head
            count = 0
            found = False
            while current != None and not found:
                count += 1
                if current.get_value() == value:
                    found = True
                else:
                    current = current.get_next()
            if found:
                return count
            else:
                raise ValueError('%s is not in linkedlist' % value)
    
        # remove删除链表中的某项元素
        def remove(self, value):
            current = self._head
            pre = None
            while current != None:
                if current.get_value() == value:
                    if not pre:
                        self._head = current.get_next()
                    else:
                        pre.set_next(current.get_next())
                        break
                else:
                    pre = current
                    current = current.get_next()
    
        # insert链表中插入元素
        def insert(self, pos, value):
            if pos <= 1:
                self.add(value)
            elif pos > self.size():
                self.append(value)
            else:
                temp = Node(value)
                pre = None
                current = self._head
                count = 1
                while count < pos:
                    count += 1
                    pre = current
                    current = current.get_next()
                pre.set_next(temp)
                temp.set_next(current)