python - 如何在 python 中将数据插入到单链表的中间?
问题描述
节点类和 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
如您所见,已经有在头部添加和在尾部添加的功能,但是我不知道如何在列表中间添加。我需要创建一个获取新数据的函数,并在单链表中间添加一个带有数据的节点。有人可以向我展示代码或如何修改这些功能之一或添加新功能吗?感谢帮助!
解决方案
您必须从第一个元素开始,然后遍历列表,直到到达要插入的位置。假设您需要node_to_insert
向 position添加一个节点pos
:
current_node = self.get_head()
for i in range(pos): # iterate pos time:
current_node = current_node.get_next() # Jump to next node
# Now curr node is `pos`-th node. We insert `node_to_insert` here.
# Suppose u already have it named `node_to_insert`.
# We need to store the next node (of current node),
# so we can link the inserted node to it
next_current_node = current_node.get_next()
current_node.set_next(node_to_insert)
node_to_insert.set_next(next_current_node)
就这样。希望这有帮助。我没有测试代码,但我希望你明白我的想法。
推荐阅读
- dart - 如何在我的应用中更改页面上的方向
- java - Mapstruct 隐式调用具有多个参数的其他映射器
- javascript - 标签点击上的触发器(“更改”)不起作用
- c# - 服务器返回对象的普通列表而不是 ODATA 信封
- c++ - 如何在我的代码中调用默认 Windows 凭据?
- excel - Excel 二次排序不起作用。手动或使用 VBA 有什么解决方法吗?
- c# - 在接收命令时通过 TCP 发送字符串
- javascript - 如何使用 JavaScript 将 ChargeBee 链接添加到 HTML 元素?
- java - JND InvalidSearchFilterException - 如何在 LDAP 中搜索规范名称?
- python - 在 plt.plot 上将 pd.Grouper 转换为人类可读的格式