使用字典和链表python

Question

我有一个字典，它的键是一个单词，我想在元素中保存一个链表，就像这样

字典

• 关键元素
• 嗨linkedlist1
• 你好linkedlist2

我已经用数组

dictionari={}
for textoactual in texto:
    archi = open(textoactual,'r')
    lines = archi.readlines()
    for row in lines:
        for word in row.split(' '):
            if word in dictionari:
                aux = dictionari[word] 
                aux_txt = textoactual.replace('.txt','')
                if not(aux_txt in aux): 
                    aux.append(aux_txt)
                    dictionari[word]=aux
            else:
                aux_txt = textoactual.replace('.txt','')
                dictionari[word] = makelist(aux_txt)

Answer 1

EDIT3这对节目来说可能太晚了，因为这个问题一个多月前就被接受了，但是我有一些东西要补充。

事实上，Python有一个标准的C-ish链表实现，它是collections模块中的deque类。这是来源

一个dequeobject由一个block节点的双链表组成。

所以如果你需要Python中的快速链表，请坚持使用deque。

EDIT2基于OP的评论

…因为我想看看哪个链表或数组更快，当我搜索信息

链表中的搜索复杂度等于数组(或基于数组的结构)中的搜索复杂度，并且大约为O(n)，其中n是容器中元素的数量。但是，由于Python内置的数据结构经过了大量优化和c语言加载，因此它们在实际使用中运行速度要快得多。当您需要在列表的任何位置恒定时间插入/删除时，或者当您不想弄乱动态大小的数组时，链表是有用的，但它似乎不适合您的情况。由于您实际上正在寻找快速搜索，因此需要一个哈希表，因此使用set s来存储文件名。为了做到这一点，替换match_words_and_files

中的以下行

res.setdefault(word, llist.LinkedList()).insert_with_lookup(file_title)

res.setdefault(word, set()).add(file_title)

编辑。OP更新了请求。前提是LinkedList的内容保存在名为llist的单独模块中:

import os
import llist

def match_words_and_files(directory):
    directory = os.path.abspath(directory)
    res = {}
    for file_name in filter(os.path.isfile, os.listdir(directory)):
        file_title = os.path.splitext(file_name)[0]
        with open(os.path.join(directory, file_name)) as inp:
            for line in inp:
                parsed_line = line.rstrip().split()
                for word in parsed_line:
                    res.setdefault(word, llist.LinkedList()).insert_with_lookup(file_title)
    return res

原始文章。

如果你想在Python中使用链表，它可以这样实现(显然这不是唯一的方法)

class Node(object):
    __slots__ = ["_data", "_next_node"]
    def __init__(self, data, next_node=None):
        self._data = data
        self._next_node = next_node
    def __str__(self):
        return str(self._data)
    def __repr__(self):
        return repr(self._data)
    @property
    def data(self):
        return self._data
    @property
    def next_node(self):
        return self._next_node
    def link_node(self, next_node):
        if not hasattr(next_node, "_next_node"):
            self._next_node = Node(next_node)
        self._next_node = next_node

class LinkedList(object):
    def __init__(self, head=None):
        if head is not None and not isinstance(head, Node):
            self._head = Node(head)
        else:
            self._head = head
    def __repr__(self):
        return repr([repr(node) for node in self.iter_links()])
    def __str__(self):
        return ','.join(str(node) for node in self.iter_links())
    def __len__(self):
        return sum(1 for _ in self.iter_links())
    def set_head(self, head):
        self._head = head
    def insert(self, node):
        if not isinstance(node, Node):
            node = Node(node)
        node.link_node(self._head)
        self._head = node
    def insert_with_lookup(self, node):
        """
        Inserts a node if the data it contains is not equal to the one
        stored in the the head node.
        """
        if not isinstance(node, Node):
            node = Node(node)
        if node.data != self._head.data:
            self.insert(node)            
    def iter_links(self):
        current_node = self._head
        while current_node:
            yield current_node
            current_node = current_node.next_node

linked_list = LinkedList(1)
linked_list.insert(2)
linked_list.insert(3)

让我们创建一个，并把它变大一点

print(list(linked_list.iter_links()))

输出:

[3, 2, 1]

公立小学

我看不出有什么理由在你的情况下使用链表