数据结构之链表

1. 创建链表元素类
2. 创建链表类
3. 为链表类创建方法函数

1.创建链表元素类

链表是由一个个元素链接而成的。所以第一步，我们先创建一个链表元素类，来表示我们的链表上的元素。接着我们通过 __init__ 方法给它定义两个属性，self.value和self.next 。

class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None

2.创建链表类

一个链表在最初被创建的时候，它至少需要一个元素。

链表是由元素链接而成，它的第一个元素，我们称它为头部元素。所以我们在__init__方法里给链表类定义了一个属性，self.head = head

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

3.为链表类创建函数方法

• append方法
• get_position方法
• insert方法
• delete方法

我们将为链表类创建以上四个方法。

append方法

​ 在链表的后面增加一个元素。链表中不能像列表那样通过索引定位每个元素。所以需要不断调用 链表元素的.next方法来不断获取下一个元素，最后获取到最后一个元素。然后在最后一个元 素的.next属性里指向新增的元素。

def append(self, new_element):
    current = self.head
    if self.head:
        while current.next:
            current = current.next
        current.next = new_element
    else:
        self.head = new_element

get_position方法

​ 获取链表中与传入参数对应的元素位置。例：get_position(1) 将会获取链表中第一个元素。

​ 这里我们依然需要通过循环调用.next属性来遍历链表。不同的是我们需要定义一个变量counter来记录我们遍历的链表元素顺序。我们还需要在传入的参数获取不到链表元素时返回None

def get_position(self, position):
    counter = 1
    current = self.head
    if position < 1:
        return None
    While current and counter <= position:
        if counter == position:
            return current
        current = current.next
        counter += 1
    return None

insert方法

​ insert方法有两个参数，new_element和position，new_element表示要插入的元素，position表示要插入链表的位置。

​ 同样的我们需要使用循环，也需要counter来记录我们遍历链表的顺序。通常我们插入元素时，都是从链表的中间插入。所以先不考虑把元素插入链表头部的情况。现在我们来想象一下，假设我们想把元素new_element插入到链表中第三个位置，也就是position为3的时候，我们需要获取什么？ 我们实际只需要获取到它的前一个元素(我们假设这个元素为element2)，也就是position为2的元素，然后把element2.next赋值给new_element.next，然后再把new_element赋值给element2.next。于是，我们便完成了元素的插入，最后再考虑插入头部的情况，我们直接把self.head赋值给new_element.next`。

def insert(self, new_element, position):
    counter = 1
    current = self.head
    if position > 1:
        while current and counter < position:
            if counter == position - 1
                new_element.next = current.next
                current.next = new_element
            current = current.next
            counter += 1
    elif position == 1:
        new_element.next = self.head 
        self.head = new_element

delete方法

​ delete删除一个value属性与传入参数“value”相同的元素。

​ 在链表中，要删除一个元素，只需要，把被删除元素前面一个元素指向到被删除元素的后一个元素。这里我们用previous来表示被删除元素的前一个元素。

def delete(self, value):
    current = self.head
    previous = None
    while current.value != value and current.next:
        previous = current
        current = current.next
    if current.value == value:
        if previous:
            previous.next = current.next
        else:
            self.head = current.next