双向链表的排序列表
Sorted List for Doubly Linked List
我有以下 2 个 classes 节点和双向链表
class DLLNode(object):
def __Init__ (self, data, prev_node=None, next_node=None):
self.data=data
self.prev_node=prev_node
self.next_node=next_node
def __str__(self):
return str(self.data)
class DoublyLinkedList(object):
def __init__(self, head=None, tail=None):
self.head=head
self.tail=tail
self.size=0
def add_to_head(self, data):
newNode = DLLNode(data)
if self.head==None:
self.head=self.tail=newNode
self.head.prev_node=self.tail.next_node=None
else:
self.head.prev_node=newNode
newNode.next_node=self.head
self.head=newNode
def add_to_tail(self, data):
newNode=DLLNode(data)
if self.head==None:
self.head=self.tail=newNode
self.head.prev_node=self.tail.next_node=None
else:
self.tail.next_node=newNode
newNode.prev_node=self.tail
self.tail=newNode
self.tail.next_node=None
def remove_head(self):
node=self.head
if self.head==self.tail:
self.prev_node=self.next_node=self.head=self.tail=None
return
if self.head!=self.tail:
node=node.next_node
node.prev_node=None
self.head=node
def remove_tail(self):
node=self.tail
if self.head==self.tail:
self.prev_node=self.next_node=self.head=self.tail=None
return
if self.head!=self.tail:
self.tail=node.prev_node
self.tail.next_node=None
def index(self,element):
current = self.head
while current != None:
if current.data == element:
return current.position
else:
current = current.next
return -1
我想创建第三个 class 名为 SortedList,它是 DoublyLinkedList class 的子class。 class 应该有 add 和 remove 向列表中添加和删除对象,并保持列表排序。还有一个 'middle' 方法到 return 列表的中间元素。不确定我应该如何创建这个 class,有点困惑。
如果您希望列表保持排序状态,请确保将元素插入排序位置。找到这个位置应该很简单。
双向链表class,只有一个双端队列(dequeue)接口,所以目前的方法实际上不能插入,你需要自己写。
此外,扩展双向链表没有多大意义,因为 add_to_head 和 add_to_tail 方法对于只允许单个 "insert"(可能叫'add',名称不重要)可能会把东西放在头部或尾部,但可以放在任何地方。因此,您可能需要考虑不同的继承层次结构。
最后,为了跟踪中间元素,您需要确定中间在偶数长度列表的上下文中的含义,然后当您:
- 在列表中间之前插入一些东西,您可能需要将中间部分更改为其前身
- 在列表中间之后插入一些东西,您可能需要将中间更改为它的后继者,
- 删除列表中间之前的内容,您可能需要将中间更改为它的后继者
- 删除列表中间部分之后的内容,您可能需要将中间部分更改为其前身
- 删除列表的中间,您需要将中间设置为它的前导或后继
具体如何处理这些情况取决于您如何定义偶数长度列表的中间部分以及列表是变为偶数还是奇数长度。请务必仔细考虑每个案例,确保它们全部正确。
我有以下 2 个 classes 节点和双向链表
class DLLNode(object):
def __Init__ (self, data, prev_node=None, next_node=None):
self.data=data
self.prev_node=prev_node
self.next_node=next_node
def __str__(self):
return str(self.data)
class DoublyLinkedList(object):
def __init__(self, head=None, tail=None):
self.head=head
self.tail=tail
self.size=0
def add_to_head(self, data):
newNode = DLLNode(data)
if self.head==None:
self.head=self.tail=newNode
self.head.prev_node=self.tail.next_node=None
else:
self.head.prev_node=newNode
newNode.next_node=self.head
self.head=newNode
def add_to_tail(self, data):
newNode=DLLNode(data)
if self.head==None:
self.head=self.tail=newNode
self.head.prev_node=self.tail.next_node=None
else:
self.tail.next_node=newNode
newNode.prev_node=self.tail
self.tail=newNode
self.tail.next_node=None
def remove_head(self):
node=self.head
if self.head==self.tail:
self.prev_node=self.next_node=self.head=self.tail=None
return
if self.head!=self.tail:
node=node.next_node
node.prev_node=None
self.head=node
def remove_tail(self):
node=self.tail
if self.head==self.tail:
self.prev_node=self.next_node=self.head=self.tail=None
return
if self.head!=self.tail:
self.tail=node.prev_node
self.tail.next_node=None
def index(self,element):
current = self.head
while current != None:
if current.data == element:
return current.position
else:
current = current.next
return -1
我想创建第三个 class 名为 SortedList,它是 DoublyLinkedList class 的子class。 class 应该有 add 和 remove 向列表中添加和删除对象,并保持列表排序。还有一个 'middle' 方法到 return 列表的中间元素。不确定我应该如何创建这个 class,有点困惑。
如果您希望列表保持排序状态,请确保将元素插入排序位置。找到这个位置应该很简单。
双向链表class,只有一个双端队列(dequeue)接口,所以目前的方法实际上不能插入,你需要自己写。
此外,扩展双向链表没有多大意义,因为 add_to_head 和 add_to_tail 方法对于只允许单个 "insert"(可能叫'add',名称不重要)可能会把东西放在头部或尾部,但可以放在任何地方。因此,您可能需要考虑不同的继承层次结构。
最后,为了跟踪中间元素,您需要确定中间在偶数长度列表的上下文中的含义,然后当您:
- 在列表中间之前插入一些东西,您可能需要将中间部分更改为其前身
- 在列表中间之后插入一些东西,您可能需要将中间更改为它的后继者,
- 删除列表中间之前的内容,您可能需要将中间更改为它的后继者
- 删除列表中间部分之后的内容,您可能需要将中间部分更改为其前身
- 删除列表的中间,您需要将中间设置为它的前导或后继
具体如何处理这些情况取决于您如何定义偶数长度列表的中间部分以及列表是变为偶数还是奇数长度。请务必仔细考虑每个案例,确保它们全部正确。