Как Python представляет LinkedList с точки зрения обращения к памяти? - PullRequest
Новая
       108

Как Python представляет LinkedList с точки зрения обращения к памяти?

0 голосов
/ 14 июля 2020

Примечание: я предпочитаю не использовать какой-либо внешний модуль, поскольку он предназначен для подготовки к собеседованию.

Я знаю, что в python нет встроенного DS со связанными списками. Однако мы можем реализовать связанный список через класс Node. В следующем коде я применил метод (Intercct_ll) для поиска пересечения между двумя связанными списками, где определение пересечений: узлы находятся в том же порядке и значениях в обоих связанных списках: 

class Node: 
  def __init__(self, data=None, next=None): 
    self.data = data
    self.next = next

class SingleLinkedList: 
  def __init__(self): 
    self.head = None

  def add_node(self, data):
    newNode = Node(data)
    
    if self.head:
        current = self.head
        while current.next: 
            current = current.next
        current.next = newNode

    else: 
        self.head = newNode
     
  def print_ll(self):
    current = self.head
    ll_data = []
    while current:
        ll_data +=  [current.data] 
        current = current.next
    return ll_data

  def intesect_ll (self, first_ll, second_ll):

    current_first = first_ll.head
    current_second = second_ll.head
     
    if current_first is None or current_second is None: 
        return False

    list_intersect = []

    while current_first and current_second:
        
        if current_first.data == current_second.data:
            list_intersect += [current_first.data] 
            
           
        current_first = current_first.next
        current_second = current_second.next
    
    for item in list_intersect:
        self.add_node(item)
    
    return self.print_ll()

Мой вопрос: :

  • Я новичок в python, поэтому я изо всех сил пытаюсь понять, почему сравнение по ссылке в памяти не работает. Другими словами, почему python не дал этим двум узлам с одинаковым значением и порядком в обоих связанных списках одно и то же место в памяти?!. Это потому, что я реализую свою собственную структуру данных и, следовательно, я предполагаю, что python позаботится обо всем остальном, что не является реальностью?

    если current_first равно current_second

результат компилятора : он дает две разные ссылки на память для обоих узлов с одинаковым значением и порядком в обоих связанных списках. Следовательно, это не работает, и тогда необходимо выполнить сравнение (.data) по значению.

1 Ответ

0 голосов
/ 14 июля 2020

Я обнаружил, что то, что я ожидаю от python с точки зрения управления памятью, на самом деле происходит не так. Мне нужно выделить один и тот же объект, а затем сослаться на него в обоих связанных списках, чтобы сравнение по ссылке стало допустимым решением. 

assign ObjectA : locationA in memory
linkedlist1: node.next --> LocationA ---> n nodes
linkedlist2:  node.next --> LocationA ----> k nodes

В противном случае это два совершенно разных связанных списка, и интерпретатор назначит каждый из них узлов в другое место памяти: 

linkedlist1: node.next ---> locationX -- n nodes
linkedlist2: node.next ---> locationY --- k nodes

Надеюсь, что это поможет любому, у кого возникнет такая же проблема

...