Q3：整数序列保存在双向链表中，实现如下操作：（20分） （1）创建； （2）遍历输出； （3）按值查找； （4）按位序插入； （5）按位序删除；

以下是Python代码实现：

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

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

    def create(self, values):
        for value in values:
            self.append(value)

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.length += 1

    def traverse(self):
        curr_node = self.head
        while curr_node is not None:
            print(curr_node.value, end=' ')
            curr_node = curr_node.next
        print()

    def search(self, value):
        curr_node = self.head
        while curr_node is not None:
            if curr_node.value == value:
                return curr_node
            curr_node = curr_node.next
        return None

    def insert(self, pos, value):
        if pos < 0 or pos > self.length:
            print('Invalid position')
            return
        new_node = Node(value)
        if pos == 0:
            if self.head is None:
                self.head = new_node
                self.tail = new_node
            else:
                new_node.next = self.head
                self.head.prev = new_node
                self.head = new_node
        elif pos == self.length:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        else:
            curr_node = self.head
            for i in range(pos-1):
                curr_node = curr_node.next
            new_node.prev = curr_node
            new_node.next = curr_node.next
            curr_node.next.prev = new_node
            curr_node.next = new_node
        self.length += 1

    def delete(self, pos):
        if pos < 0 or pos >= self.length:
            print('Invalid position')
            return
        if pos == 0:
            if self.head.next is None:
                self.head = None
                self.tail = None
            else:
                self.head = self.head.next
                self.head.prev = None
        elif pos == self.length-1:
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            curr_node = self.head
            for i in range(pos):
                curr_node = curr_node.next
            curr_node.prev.next = curr_node.next
            curr_node.next.prev = curr_node.prev
        self.length -= 1

使用样例：

ll = LinkedList()
ll.create([1, 2, 3, 4, 5])
ll.traverse()  # 1 2 3 4 5
print(ll.search(3).value)  # 3
ll.insert(2, 6)
ll.traverse()  # 1 2 6 3 4 5
ll.delete(4)
ll.traverse()  # 1 2 6 3 5