非常不好意思的又来向大家问小白问题了，关于 python3

在不创建新的 dictionary 或者 list 或者 linked list 情况下，怎么清空 linked list 里面的所有东西？
简单来说就是通过把 pointer 移来移去，删除 linked list 里面的东西。
删除过后 linked list 应该 print 出来 None

如果允许创建新的 list ，这我也会。
可不被允许我就没辙了。。。。%>_<%
求大家帮帮忙 T^T

第 1 条附言 · 2016-03-07 07:16:59 +08:00

各位我错了。这个是我创建 linked list 的代码。不知道怎么删除，所以那部分还没写。
readFile 会在 main 里面 call 两遍读取两个 txt 文件并存成两个单独的 linked list 。
PS. 请大家不要纠结 PEP8 还有格式之类的啦~~老师这么要求的我也木有办法╮(╯_╰)╭

http://imgur.com/WBvRayM

现在有点忙直接截了个图给大家。希望大家不要被嫌弃。

list

linked

删除

创建

44 条回复 • 2016-03-09 09:09:50 +08:00

Cassandra

2016-03-06 22:29:34 +08:00

啊我忘说了！ recursion 和 class 都没学。老师应该也不会允许

evolsnow

2016-03-06 22:51:43 +08:00

del l[:]?

Cassandra

2016-03-06 22:54:16 +08:00

@evolsnow 并不能行

lxy42

2016-03-06 23:13:10 +08:00

l[：] = []

Cassandra

2016-03-06 23:15:42 +08:00

@lxy42 这个也不行哦

Strikeactor

2016-03-06 23:54:19 +08:00

原谅我完全没看明白楼主在问什么

magicdawn

2016-03-06 23:57:23 +08:00

@lxy42

`l[:] = []` 这个创建了新的 list

Cassandra

2016-03-06 23:59:11 +08:00

@Strikeactor 额是哪里没有懂呢

yelite

2016-03-07 00:01:53 +08:00 via iPhone

你的 linked list 是用什么表示的？
我记得 list 是有个 clear 方法的

Cassandra

2016-03-07 00:06:34 +08:00

@yelite 额类似 dictionary 的写法 node = {} node['data'] = value node['next'] = None 这种？不知道你是不是想要问这个

yelite

2016-03-07 00:11:59 +08:00 via iPhone

@Cassandra 应该还要有一个变量指向 last node 或者 first node ？把它变成 None 就行了

Strikeactor

2016-03-07 00:12:39 +08:00

@Cassandra 全部，我猜你想问的是数据结构的问题，然而把锅丢到了 python 头上

Cassandra

2016-03-07 00:19:04 +08:00

@Strikeactor 并不能完全算是数据结构问题吧。我就是想问问如何删除 linked list 里的所有东西。然后我就是用 python 在写。嗯。

@yelite 好我试试

Cassandra

2016-03-07 00:21:26 +08:00

@yelite 有一个变量指向 first node 。直接把它变成 none 好像不行哦。不过老师的确是要求通过更改这个变量指向的位置来删除

shutongxinq

2016-03-07 00:26:26 +08:00

@Cassandra 假设 curNode 指向 head ，你就
while curNode:
curNode = curNode.next
就可以了

yelite

2016-03-07 00:28:07 +08:00 via iPhone

@Cassandra 那也可以用循环， first_node = first_node['next'] 直到变成 None 。不过和直接写没有任何区别…

seki

2016-03-07 00:39:37 +08:00

到底是用什么构造出来的 linked list ？
删除又是什么概念，在 python 没有引用就会被回收，直接改成 None ，就可以看作被删除了

这些看上去是用 c 来写数据结构的问题，用 python 写就感觉怪怪的

cosven

2016-03-07 00:41:11 +08:00

怎么看都像 c 家族的问题，嘿嘿 -- - - - - 个人感觉

感觉 LZ 的问题是怎样释放(单)链表

1. 应该不能从 head (第一个节点) 指针开始释放
2. 也不方便从 tail (最后一个指针) 开始释放。（如果是单链表的话）

个人感觉：从第二个节点开始释放

```c/c+_+
tmp = head->next->next
free(head->next)
head->next = tmp
```
多年没写过 c 的感觉应该是这样....
不对勿喷....

Cassandra

2016-03-07 00:47:00 +08:00

@seki
@cosven
老师教的使用 dictionary 构造 linked list 。我不是很了解 c 所以也不知道为什么你们这么说。可是老师这么教，总要这么写吧，学生嘛还是要分数的。
不过很好奇在 python 下你们怎么构造 linked list 呢

cosven

2016-03-07 00:49:56 +08:00

# -*- coding: utf-8 -*-

class LinkedList(object):
def __init__(self, val=0):
self.val = val
self.next_ = None

def main():
l1 = LinkedList(1)
l2 = LinkedList(2)
l3 = LinkedList(3)

l1.next_ = l2
l2.next_ = l3

print(l1.val)
while(l1.next_):
if not l1.next_.next_:
del l1.next_
break
tmp = l1.next_.next_
del l1.next_
l1.next_ = tmp

del l1
# print(l1.val)

if __name__ == '__main__':
main()

cosven

2016-03-07 00:51:55 +08:00

这边没有高亮，看起来有点痛苦。
我贴了个简单的示例在 github 上。 https://github.com/cosven/cosven.github.io/issues/19

Cassandra

2016-03-07 00:52:28 +08:00

@cosven 这样啊。确实可能好一些。可是 class 还没学。╮(╯_╰)╭

kendetrics

2016-03-07 00:57:14 +08:00

@Cassandra 因为高级语言里有些特性是已经被封装好了的，同时对性能不像底层语言那么重视。链表是为了代替数组达到增加或者删除元素时不造成之后的元素大量的位移的结构，然而 Python 里你要删 list 的一个元素直接 del 就可以了。

你如果想知道链表应该怎么删除元素，就把 python 相关的都删了纯问数据结构。如果想知道你的作业怎么完成，就把你的链表的实现代码发上来让大家帮你改。原文中的描述 linked list 是自己实现的，“通过把 pointer 移来移去”、“ print 出来 None ”等描述在没有你的代码的情况下看得一脸糊是很正常的。

manfay

2016-03-07 01:17:03 +08:00 via iPad

是在 class 里面操作还是在外面调用方法操作呢？
如果在里面，可以参照 __init__ 里创建空链表的方式来弄。
如果在外面，它肯定有一个 remove 或者 delete 方法啊（没有就自己写一个），删到变空为止就好了。

cosven

2016-03-07 01:27:34 +08:00

确实像 kendetrics 说的那样，最好把自己的代码贴出来。这样比较有针对性。

我想了下用 dict 构造链表，会有一些潜在的问题。比如下面这个例子。

l1 = dict(val=1, next_=None)
l2 = dict(val=2, next_=None)

l1['next_'] = l2

del l1['next_']
print l2['val'] # 输出为 2 ，所以实际上 l2 这个变量并没有完全被 delete 掉。

Cassandra

2016-03-07 02:16:22 +08:00

@kendetrics
@cosven
我也想过把代码贴出来。但是因为不知道怎么在不创建新的 list 的情况下删除所有的，所以还没写。
我要是把怎么创建 linked list 代码 po 出来会有帮助吗？
@manfay 没有用到 class 呢。

haoc

2016-03-07 06:09:01 +08:00

你把问题弄明白了在问好咩？
python 会自己做 GC ，没有 ref 就会被回收了。不用自己删除吧。

binux

2016-03-07 06:22:41 +08:00

@Cassandra 你不把你怎么创建链表的代码贴出来，怎么知道你是怎么用 dict 构建的链表的。正常人可不会这么干。

（我猜是用 dict 模拟类，{'data': 1, 'next': {}} 之类的）

Cassandra

2016-03-07 06:59:03 +08:00

@haoc 可是不手动删除， print 出来的话所有的 node 肯定都还在呀

chinuno

2016-03-07 07:40:06 +08:00

删除 aList 里面所有 node ？直接把 aList 赋值成 None 就行了。原来的东西会自动回收掉

chinuno

2016-03-07 07:58:36 +08:00

用 python 教数据结构也是奇葩。链表本来就是要通过指针来做操作的东西， Python 没有指针只能模拟。始终是模拟出来的东西要理解它的本质不太直观。我猜你们是用{addr:node}这样模拟的

manfay

2016-03-07 09:20:42 +08:00 via iPad

楼主，看你的代码，你注意看里面都写了什么时候是 empty 了

# accounting for cases that the list is empty
If (ptr == none) ......

也就是说，如果你的链表的值等于 none ，链表就会被当作 empty 。
那你直接写 aList = none 不就可以了吗。

Cassandra

2016-03-07 09:54:21 +08:00

@manfay 主要是在另一个 function 里面要把它全都删除。这个只是创建 linked list 的方式。

ming2281

2016-03-07 10:14:59 +08:00

楼主可以看 list 的 pop 方法, 我帮你贴一下
L.pop([index]) -> item -- remove and return item at index (default last).
Raises IndexError if list is empty or index is out of range.
Type: builtin_function_or_method

manfay

2016-03-07 10:59:24 +08:00

@Cassandra 假设你的 aList 里有 3 个 item ，你一个个删，删到剩下最后一个的时候，就属于遇到了特殊情况，最后你不得不这样写 if ( len(prt) == 1): prt = None

而且这不是创建吧，创建时你的 aList 的类型就不是 None ，而是 dict ，它有且只有两个 key （"data"和"next"），其中 next 要么指向 None ，要么指向另一个 dict 。

Cassandra

2016-03-07 11:42:03 +08:00

@manfay readFile()只是读取，在它里面 call 了 addToEnd(), 这个 function 才是真正的创建

manfay

2016-03-07 12:09:01 +08:00

@Cassandra 如果是清空 linked list ，完全不用一个个删除。但是如果你真的想一个个删，也很简单，比如可以这样：

next = aList["next"]
aList = next

这就把头一个 item 给删除啦~

对于 linked list ，通常能做的事情就是顺藤摸瓜，比如我上面第一句，就是“摸”出下一个 item 来，然后把这个摸出来的（本来是第二个 item ）当作 head ，直接忽略了原来的 head ，相当移动了指针。

Cassandra

2016-03-07 12:14:33 +08:00

@manfay 好的等这段时间忙完我试一试

Frapples

2016-03-07 13:01:35 +08:00

拿 python 写链表是什么鬼。。。。？
清空链表的思路大体是，用一个变量指向第一个节点，删掉该节点后再后移，如此循环。但是注意的是删除该节点后下个节点的信息就丢了，因此还要提前保存下个节点的信息。
代码大约是这样：
def delete(linkedList):
p = linkedList
while p is not None:
next = p['next']
// 删除数据
p = next

你没发现那个 linkedList 只要有变量指向它，链表的节点就没办法被干掉吗？。。。。

Frapples

2016-03-07 13:14:04 +08:00

@Cassandra
看了下上面的回复，其实用没有指针变量的语言写链表的正确方法是这样的：
首先要用该语言的线性数组来储存节点空间（ python 中是 list ）。这样，我们就可以把一个整型数代替 C 中的内存地址来使用。整型数表示的是节点在节点数组中的下标。
程序启动时，节点数组中的空闲节点要串起来组成一个链表，叫空闲链表。然后我们可以模拟 malloc 和 free 了, malloc 会从空闲链表中移除一个节点供使用， free 会把不用的节点回收到空闲链表里。

这种方法叫做游标实现法，参考自《数据结构与算法分析》第 43 页。

不晓得你看懂了没。。。链表这东西还是用 C 之类的语言实现比较明了。。。

Frapples

2016-03-07 13:19:21 +08:00

忘记说了，以上只是模拟出了 malloc 和 free ，有了这两个之后才能开开心心的实现链表了。

kkzxak47

2016-03-07 15:28:41 +08:00

head = readFile('path to file')
p = head

while p is not None:
this = p
p = p['next']
this['data'] = None # or del this['data']?
this['next'] = None # or del this['next']?

说实在的，根据你描述“删除过后 linked list 应该 print 出来 None ”难道不是写一句 head = None 就结束了么……

Cassandra

2016-03-07 22:59:52 +08:00

@kkzxak47 老师大概不会这么 check

wizardforcel

2016-03-09 09:09:50 +08:00 via Android

直接把 head 置为 None 就行了。

由于没有循环引用（你也得保证你的链表不成环），引用计数可以正常工作。

实际上，复杂对象里面的引用是树结构的，你这个链表根本不算什么。