节点类和SingleLinkedList类代码:
class Node():
'''represents a node as a building block of a single linked list'''
def __init__(self, element, next_node=None):
'''(Node, obj, Node) -> NoneType
construct a node as building block of a single linked list'''
self._element = element
self._next = next_node
def set_next(self, next_node):
'''(Node, Node) -> NoneType
set node to point to next_node'''
self._next = next_node
def set_element(self, element):
'''(Node, obj) ->NoneType
set the _element to a new value'''
self._element = element
def get_next(self):
'''(Node) -> Node
returns the reference to next node'''
return self._next
def get_element(self):
'''(Node) -> obj
returns the element of this node'''
return self._element
def __str__(self):
'''(Node) -> str
returns the element of this node and the reference to next node'''
return "(" + str(self._element) + ", " + str(hex(id(self._next))) + ")"
class SingleLinkedList():
''' represents a single linked list'''
def __init__(self):
'''(SingleLinkedList) ->NoneType
initializes the references of an empty SLL'''
self._size = 0
self._head = None
self._tail = None
self._value = None
self._next = None
def set_head(self, new_head):
'''(SingleLinkedList) -> None
updates the head'''
self._head = new_head
def set_tail(self, new_tail):
'''(SingleLinkedList) -> None
updates the tail'''
self._tail = new_tail
def get_head(self):
'''(SingleLinkedList) -> Node
Return the pointer to the head'''
return self._head
def get_tail(self):
'''(SingleLinkedList) -> Node
Return the pointer to the tail'''
return self._tail
def is_empty(self):
'''(SingleLinkedList) -> bool
returns true if no item is in this SLL'''
return self._size == 0
def size(self):
'''(SingleLinkedList) -> int
returns the number of items in this SLL'''
return self._size
def add_first(self, element):
'''(SingleLinkedList, obj) -> NoneType
adds a node to the first of the SLL'''
# create a node that point to the head
node = Node(element, self._head)
# let head point to the node
self._head = node
# if this node is the first node in this SLL, tail should point to this node too
if (self._size == 0):
self._tail = node
# increment the size
self._size += 1
def add_last(self, element):
'''(SingleLinkedList, obj) -> NoneType
adds a node to the end of this SLL'''
# create a node with the given element that points to None
node = Node(element, None)
# let the _next part of the tail to point to newly created node
self._tail.set_next(node)
#let tail to point to the added node
self._tail = node
# if this node is the first node in this SLL, let head to point to this node too
if (self._size == 0):
self._head = node
# increment the size
self._size += 1
def remove_first(self):
'''(SingleLinkedList, obj) -> obj
remvoe the node from the head of this SLL and returns the element stored in this node'''
# sset element to None in case SLL was empty
element = None
# if SLL is not empty
if (self._head is not None):
# get the first node
node = self._head
# let head point to the second node
self._head = self._head.get_next()
# decrement the size
self._size -= 1
#set the _next of previous head to point to None (for garbage collection purpose)
node.set_next(None)
# get the element stored in the node
element = node.get_element()
#return the element of the removed node
return element
def __str__(self):
'''(SingleLinkedList) -> str
returns the items in the SLL in a string form
'''
# define a node, which points to the head
cur = self._head
# define an empty string to be used as a container for the items in the SLL
result = ""
# loop over the SLL until you get to the end of the SLL
while (cur is not None):
# get the element that of the current node and attach it to the final result
result = result + str(cur.get_element()) + ", "
# proceed to next node
cur = cur.get_next()
#enclose the result in a parantheses
result = "(" + result[:-2] + ")"
#return the result
return result
正如您所看到的,已经有一些函数可以添加在头部和尾部,但是我不知道如何添加到列表的中间。我需要创建一个函数来获取新数据,并在singlelinkedlist的中间添加一个包含数据的节点。有人能告诉我代码或如何修改这些功能之一或添加一个新的?谢谢你的帮助!你知道吗
这应该起作用:
测试:
必须从第一个元素开始,然后遍历列表,直到到达要插入的位置。假设您需要将节点
node_to_insert
添加到位置pos
:仅此而已。希望这有帮助。我没有测试代码,但我希望你能理解我的想法。你知道吗
相关问题 更多 >
编程相关推荐