博客

链表是节点的集合。第一个节点(Node)一般被称为Head。最后一个节点的Next属性必须指向 None ，表明是链表的结尾。

在大多数编程语言中，链表和数组在内存中的存储方式存在明显差异。数组要求内存空间是连续的，链表可以不连续。

然而，在 Python 中，list是动态数组。所以在Python中列表和链表的内存使用非常相似。

链表和数组在以下的操作中也有本质区别：

1.插入元素：数组中插入元素时，插入位置之后的所有元素都需要往后移动一位，所以数组中插入元素最坏时间复杂度是 O(n)链表可以达到 O(1) 的时间复杂度。

2. 删除元素：数组需要将删除位置之后的元素全部往前移动一位，最坏时间复杂度是 O(n)，链表可以达到 O(1) 的时间复杂度。

3.随机访问元素：数组可以通过下标直接访问元素，时间复杂度为O(1)。链表需要从头结点开始遍历，时间复杂度为O(n)。

4.获取长度： 数组获取长度的时间复杂度为O(1)，链表获取长度也只能从头开始遍历，时间复杂度为O(n)。


实现链表

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

在LinkedList中，需要存储的唯一信息是链表的开始位置(链表的头部)。接下来，创建另一个类Node来表示链表的每个节点：

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

我们可以给刚创建的两个类添加 __repr__ 方法, 在创建实例的时候输出更多有用的信息：

class LinkedList:
    def __init__(self):
        self.head = None
def __repr__(self):
    node = self.head
    nodes = []
    while node is not None:
        nodes.append(node.data)
        node = node.next
    nodes.append("None")
    return " -> ".join(nodes)

我们可以给刚创建的两个类添加 __repr__ 方法, 在创建实例的时候输出更多有用的信息

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

创建测试类, 测试上面的代码

from LinkedList import LinkedList
from Node import Node
if __name__ == '__main__':
    llist = LinkedList()
    print(llist)
    first_node = Node('a')
    llist.head = first_node
    print(llist)
    second_node = Node('b')
    third_node = Node('c')
    first_node.next = second_node
    second_node.next = third_node
    print(llist)

修改__init__ 方法，可以传入列表快速创建LinkedList

def __init__(self, nodes=None):
    self.head = None
    if nodes is not None:
        node = Node(data=nodes.pop(0))
    self.head = node
    for elem in nodes:
        node.next = Node(data=elem)
        node = node.next

创建__iter__ 方法，遍历链表

def __iter__(self):
    node = self.head
    while node is not None:
        yield node
        node = node.next

from LinkedList import LinkedList
if __name__ == '__main__':
    llist = LinkedList(['a','b','c','d','e'])
    print(llist)
for node in llist:

    print(node)

实现链表，添加节点

在头部添加Node：在链表的开头添加一个Node，不必遍历链表，只需将新的Node的next属性指向 self.head ，并将新的node设置为新的 self.head

def add_first(self, node):
    node.next = self.head
    self.head = node

from LinkedList import LinkedList
from Node import Node
if __name__ == '__main__':
    llist = LinkedList()
    print(llist)
    llist.add_first(Node('b'))
    print(llist)
    llist.add_first(Node('a'))
    print(llist)

在尾部添加Node：必须遍历链表，与list不同，list可以直接获取长度， 链表只有从第一个Node，不断的去获取下一个Node 才能知道链表的尾部。

def add_last(self, node):
    if self.head is None:
        self.head = node
        return
    for current_node in self:
        pass
    current_node.next = node

from LinkedList import LinkedList
from Node import Node
if __name__ == '__main__':
    llist = LinkedList(['a','b','c','d'])
    print(llist)

    llist.add_last(Node('e'))
    print(llist)

    
    llist.add_last(Node('f'))
    print(llist)

在指定元素后添加Node：遍历链表找到目标Node， 把目标Node的下一个元素， 赋值给要添加Node的next属性, 然后修改目标Node的next属性, 指向新添加的Node, 当链表为空以及目标元素不存在时抛出异常。

def add_after(self, target_node_data, new_node):
   if self.head is None:
        raise Exception("List is empty")
for node in self:
   if node.data == target_node_data:
     new_node.next = node.next
     node.next = new_node
     return
     
     raise Exception("Node with data '%s' not found" % target_node_data)

在指定元素后添加Node：遍历链表找到目标Node， 把目标Node的下一个元素， 赋值给要添加Node的next属性, 然后修改目标Node的next属性, 指向新添加的Node, 当链表为空以及目标元素不存在时抛出异常。

from LinkedList import LinkedList
from Node import Node
if __name__ == '__main__':

    llist = LinkedList()
    llist.add_after("a", Node("b"))
    llist = LinkedList(['a','b','c','d'])
    print(llist)
    llist.add_after("c", Node("cc"))
    print(llist)
    llist.add_after("f", Node("g"))

在指定元素前添加Node：遍历链表找到目标Node，还需要记录当前节点的前一个节点。

def add_before(self, target_node_data, new_node):
    if self.head is None:
        raise Exception("List is empty")

    if self.head.data == target_node_data:
        return self.add_first(new_node)
    prev_node = self.head
    for node in self:
        if node.data == target_node_data:
        prev_node.next = new_node
        new_node.next = node
        return
    prev_node = node

    raise Exception("Node with data '%s' not found" % target_node_data)

from LinkedList import LinkedList
from Node import Node
if __name__ == '__main__’:
    llist = LinkedList()
    llist.add_before("a", Node("b"))
    llist = LinkedList(["b", "c"])
    print(llist)
    llist.add_before('b',Node('a'))
    print(llist)
    llist.add_before("b", Node("aa"))
    llist.add_before("c", Node("bb"))
    print(llist)
    llist.add_before("n", Node("m"))

删除Node：遍历链表找到目标Node，将目标Node的前一个Node的next属性,指向目标Node的next节点。

def remove_node(self, target_node_data):
    if self.head is None:
        raise Exception("List is empty")
    if self.head.data == target_node_data:
        self.head = self.head.next
        return

    previous_node = self.head
    for node in self:
        if node.data == target_node_data:
        previous_node.next = node.next
        return
    previous_node = node
raise Exception("Node with data '%s' not found" % target_node_data)

from LinkedList import LinkedList
from Node import Node
if __name__ == '__main__’:
    llist = LinkedList(["a", "b", "c", "d", "e"])
    print(llist)
    llist.remove_node("a")
    print(llist)
    llist.remove_node('e')
    print(llist)