单向链表与双向链表

单向链表

链表是实现了数据之间保持逻辑顺序，但存储空间不必按顺序存放的方法。可以用一个图来表示这种链表的数据结构：

链表中的基本要素：

 1. 结点(也可以叫节点或元素)，每一个结点有两个域，左边部份叫`值域`，用于存放用户数据；右边叫`指针域`，一般是存储着到下一个元素的指针
2. head结点，head是一个特殊的结节，head结点永远指向第一个结点
3. tail结点，tail结点也是一个特殊的结点，tail结点永远指向最后一个节点
4. None或Null，链表中最后一个结点指针域的指针指向None值，因也叫接地点，所以有些资料上用电气上的接地符号代表None 

链表的实现完全可以不使用内置的数据结构来存放node数据，但为了简化逻辑以下代码使用list来存放node节点。

 # 单向链表
class SingleNode:
    """
    节点类，存储节点值及指向下一个节点的指针
    """
    def __init__(self, value):
        self.value = value
        self.next = None

    def __repr__(self):
        return str(self.value)

class LinkedList:
    def __init__(self):
        self.nodes = []   # 用于存放节点,使用list检索方便，但是插入，remove不合适
        self.head = None
        self.tail = None

    def is_empty(self):
        # 判断链表是否为空
        return self.nodes is None

    def size(self):
        # 获取链表长度
        return len(self.nodes)

    def append(self, value):
        """
        1. 链表为空时，直接把head指向node
        2. 链表不为空时，把tail指向节点的next指向node
        """
        node = SingleNode(value)
        prev = self.tail  # 取得tail指向的节点
        if prev is None:  # 说明此时是一个空的链表
            self.head = node
            self.tail = node  # tail必定指向node
        else:
            prev.next = node
            self.tail = node  # tail必定指向node
        self.nodes.append(node)
        # print(self.nodes)

    def iter_nodes(self):
        """
        遍历节点
        """
        current = self.head
        while current:
            yield current
            current = current.next

    def iter_nodes2(self):
        for i in self.nodes:  # 可借助list遍历
            yield i.value

    def search(self, value):
        # 判断value是否在链表中的值
        return value in (i.value for i in self.nodes)

    def insert(self, idx, value):
        # 插入节点，为空链表或idx越界时
        if self.head is None or idx + 1 > len(self.nodes):
            self.append(value)
        else:
            pre_node = self.nodes[idx]
            cur_node = SingleNode(value)
            self.nodes.insert(idx, cur_node)
            self.head = cur_node
            cur_node.next = pre_node

    def remove(self, idx):  # 只能以索引的方式删除，索引是唯一的，面节点的value可以重复
        if self.head is None:  # 空链表
            raise Exception('The linked list is an empty')
        elif idx > len(self.nodes) - 1:  # idx 越界
            raise Exception('Linked list length less than index')
        elif self.head == self.tail:  # 链表中只有一个node，直接删除
            self.head = None
            self.tail = None
            return self.nodes.pop()
        elif idx == 0:  # 删除第一个node
            cur = self.head
            self.head = cur.next
            return self.nodes.pop(0)
        elif idx == len(self.nodes) - 1:  # 删除最后一个node
            tail = self.nodes[-2]
            tail.next = None
            self.tail = tail
            return self.nodes.pop()
        else:
            pre = self.nodes[idx-1]
            pre.next = self.nodes[idx + 1]
            return self.nodes.pop(idx)

# 以下为链表的测试
ll = LinkedList()
ll.append(2)
ll.append(20)
ll.append(6)
inodes = ll.iter_nodes()
print(inodes)
for note in inodes:
    print(note.value)

print('='*20)
print(list(ll.iter_nodes2()))

ll.insert(2, 10)
print(ll.nodes)
print(ll.is_empty())

print('='*20)
print(ll.remove(1))
print(list(ll.iter_nodes2()))
print(ll.size())

print(ll.search(200))

# 输出
<generator object LinkedList.iter_nodes at 0x100a0e6d0>
2
20
6
====================
[2, 20, 6]
[2, 20, 10, 6]
False
====================
20
[2, 10, 6]
3
False 

引入list存放node后就把问题简单化了，本是无序的链表节点存放在list后就成了有序的了，list的引入主要是简化了 insert 和 remove 的操作，如果不引入list，那插入操作和删除操作都只能遍历链表找到相应的位置后把node插入，而引入list后就可以利用list的索引完成node的插入和删除。如果有大量的插入和删除操作，引入list不是很好的选择，这是因为在数据规模较大时，list的insert和remove开销较大。

双向链表

双向链表是在单向链表的node上增加了一个指针域。双向链表中每个节点有三部分组成，两个指针域和一个值域，第一个指针指向上一个节点，第二个指针指向下一个节点，链表中第一个节点的第一个指针指向None或Null，最后一个节点的第二个指针指向None或Null。如下图：

代码实现：

 class SingleNode:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

    def __repr__(self):
        return str(self.value)

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

    def append(self, value):
        node = SingleNode(value)
        if self.head is None:  # 为空链表时
            self.head = node
        else:  # 为非空链表时
            self.tail.next = node  # 1. 最后一个node的next指向加入的node
            node.prev = self.tail  # 2. 新加入node的prev指向加入node前最后的节点，即self.tail
        self.tail = node  # 不管链表为空或非空，最终self.tail始终都会指向append进来的node

    def iter_nodes(self, reverse=False):  # 双向链表可以反向迭代
        current = self.tail if reverse else self.head
        while current:
            yield current
            current = current.prev if reverse else current.next

    def pop(self):
        # 1. 为空链表时
        if self.head is None:
            raise Exception('Empty')
        # 获取一些基础信息
        tail = self.tail
        prev = tail.prev
        # next = tail.next
        # 2. 只有一个节点的链表时
        if prev is None:
            self.head = None
            self.tail = None
            return tail.value
        else:  # 3. 链表中节点数大于1时
            self.tail = prev  # 把链表的tail指向上一个节点
            prev.next = None  # 修正前一个node的next
            return tail.value

    def get_item(self, index):
        if index < 0:
            return None
        current = None
        for i, n in enumerate(self.iter_nodes()):
            if index == i:
                current = n
                break
        if current is not None:
            return current  # 返回节点

    def insert(self, index, value):
        if index < 0:
            raise Exception('Error')
        current = None
        for i, n in enumerate(self.iter_nodes()):
            if index == i:
                current = n
                break
        if current is None:  # 通过上边的for循环迭代后没有找到对应索引的node时，直接调用append函数在尾部追加
            self.append(value)
            return None
        prev = current.prev
        # next = current.next
        node = SingleNode(value)
        if prev is None:  # 原链表里只有一个元素，此时就在头部插入
            self.head = node
            current.prev = node
            node.next = current
        else:  # 在链表中间插入
            node.prev = prev  # 新节点的prev指向上一个节点
            node.next = current  # 新节点的next指向for循环找到的节点
            prev.next = node  # for循环找到的节点的上一个节点的next指向新节点
            current.prev = node  # for循环找到的节点的上一个节点指向新节点

    def remove(self, index):  # 使用索引，因值可能会重复
        # 需要考虑的情况：
        # 1.空链表
        # 2. 只有一个节点的链表
        # 3. 删除的是链表中第一个节点
        # 3. 删除的是链表中最后一个节点
        # 4. 索引超出界限
        if self.head is None:
            raise Exception('Empty')
        if index < 0:
            raise ValueError('Wrong Index {}'.format(index))
        current = None
        for i, n in enumerate(self.iter_nodes()):
            if index == i:
                current = n
                break
        if current is None:  # 索引超出界限
            raise ValueError('Wrong Index {}, Out of boundary'.format(index))
        prev = current.prev
        next = current.next

        if prev is None and next is None:  # 链表仅有一个节点时
            self.head = None
            self.tail = None
        elif prev is None:  # 删除链表中第一个节点时
            self.head = next
            next.prev = None
        elif next is None:  # 删除链表中最后一个节点时
            self.tail = prev
            prev.next = None
        else:  # 其他情况，剩下删除链表中的中间节点
            prev.next = next
            next.prev = prev

        del current  # 直接清理掉节点

if __name__ == '__main__':
    ll = LinkedList()
    ll.append('aaa')
    ll.append(1)
    # ll.append(2)
    # ll.append(3)
    # ll.append(4)
    # ll.append('x')
    # ll.append('y')
    # for node in ll.iter_nodes():
    #     print(node.value)
    # ll.pop()
    # ll.pop()
    # ll.pop()
    print('==========')
    ll.insert(0, 'bbb')
    # ll.insert(6, 'z')
    # ll.insert(30, 'xxxxxxxx')
    for node in ll.iter_nodes():
        print(node.value)
    print('='*20)
    ll.remove(0)
    for node in ll.iter_nodes():
        print(node.value)
 

查看更多关于单向链表与双向链表的详细内容...