Сравнение двух связанных списков

Question

Каков наилучший способ сравнить два Связанных списков в Java, у меня есть два списка и вы хотите убедиться, что ни один из элементов в одном списке не находится в другом. что-то вроде этой работы, оба списка - это списки локальных дат.

boolean doesNotContain (LinkedList L1, LinkedList L2) { 
     for(LocalDate d:L1) { 
      if(l2.contains(d){ 
       return false; 

      } 
     } 
     return true;  
}  

Answer 1

Поскольку ваша реализация doesNotContain(..) близка к реализации реализации containsAll(..), я бы предложил использовать ее. Если вы выполните list1.containsAll(list2), реализация будет циклически пересекать все элементы list2, чтобы проверить, есть ли равный объект в list1. Вот почему вам нужно переопределить public boolean equals(Object obj) в LocalDate.

Найдите ниже небольшой пример, чтобы показать, что сделано в containsAll(..)

основной процедуры для запуска проверки

public static void main(String[] args) throws Exception { 
    List<LocalDate> list1 = new LinkedList<>(); 
    list1.add(new LocalDate("112233")); 
    list1.add(new LocalDate("223344")); 

    List<LocalDate> list2 = new LinkedList<>(); 
    list2.add(new LocalDate("112233")); 
    list2.add(new LocalDate("112233")); 

    System.out.println("list1 = " + list1); 
    System.out.println("list2 = " + list2); 

    System.out.println("list1.containsAll(list2) = " + list1.containsAll(list2)); 
    System.out.println("list2.containsAll(list1) = " + list2.containsAll(list1)); 
} 

, если вы реализуете LocalDate без переопределения метода Equals, equals будет верно, только если вы сравниваете ссылки того же объекта.

// a naive implementation for demonstration purpose 
class LocalDate { 

    String hour; 
    String minute; 
    String second; 

    LocalDate(String string) { 
     hour = string.substring(0, 2); 
     minute = string.substring(2, 4); 
     second = string.substring(4, 6); 
    } 

    @Override 
    public String toString() { 
     return String.format("LocalDate{%s%s%s} - hashcode: %d", hour, minute, second, this.hashCode()); 
    } 
} 

результат будет

list1 = [LocalDate{112233} - hashcode: 33039820, LocalDate{223344} - hashcode: 31311199] 
list2 = [LocalDate{112233} - hashcode: 13177912, LocalDate{112233} - hashcode: 21924553] 
list1.containsAll(list2) = false 
list2.containsAll(list1) = false 

если вы переопределить метод Equals (хэш-код был опущен для демонстрационных целей)

@Override 
public boolean equals(Object obj) { 
    if (obj == null) { 
     return false; 
    } 
    if (getClass() != obj.getClass()) { 
     return false; 
    } 
    final LocalDate other = (LocalDate) obj; 
    System.out.println(toString() + ".equals(" + obj.toString() + ')'); 
    if (!Objects.equals(this.hour, other.hour)) { 
     return false; 
    } 
    if (!Objects.equals(this.minute, other.minute)) { 
     return false; 
    } 
    if (!Objects.equals(this.second, other.second)) { 
     return false; 
    } 
    return true; 
} 

выход будет

list1 = [LocalDate{112233} - hashcode: 33336787, LocalDate{223344} - hashcode: 12767201] 
list2 = [LocalDate{112233} - hashcode: 31311199, LocalDate{112233} - hashcode: 13177912] 
// generated output by the method containsAll(..) 
LocalDate{112233} - hashcode: 31311199.equals(LocalDate{112233} - hashcode: 33336787) 
LocalDate{112233} - hashcode: 13177912.equals(LocalDate{112233} - hashcode: 33336787) 
list1.containsAll(list2) = true 
// generated output by the method containsAll(..) 
LocalDate{112233} - hashcode: 33336787.equals(LocalDate{112233} - hashcode: 31311199) 
LocalDate{223344} - hashcode: 12767201.equals(LocalDate{112233} - hashcode: 31311199) 
LocalDate{223344} - hashcode: 12767201.equals(LocalDate{112233} - hashcode: 13177912) 
list2.containsAll(list1) = false 

на основе p rinted Object.hashcode() вы можете легко увидеть, что метод containsAll() пересекает все элементы в списке, на который вы вызываете метод.

Если вы хотите улучшить проверку Вам необходимо уточнить первый следующие моменты - это элементы в списке уникален -> то лучше использовать Set - должен список имеет одинаковое число элементов -> если да вас могут сравниваться как первый шаг их размеров - если вам нужно проверить только, что в списке2 есть только те элементы, которые находятся в списке1 (означает, что список содержит уникальные значения) -> вызов метода containsAll в списке2 - также может быть полезно отсортировать (в зависимости от содержащихся данных)

Без этой информации невозможно дать предложение, которое будет the best во всех случаях.

Answer 2

Ваше решение работает в сложности N^2. Если вы сортируете оба списка и перебираете их в одном цикле, вы можете сделать int в N log N (это сложность сортировки).

Вы также можете создать два новых Set s, содержащих элементы из обоих списков, а затем использовать метод containsAll() - он выполнит всю работу. Это чистое и понятное решение. Тем не менее, это может быть память.

Методы сравнения зависят от методов equals() и hashCode() - если вы не должным образом переопределите их в своем классе LocalDate, вы не получите хороших результатов.

BTW1: перерыв после возвращения мертвый код

BTW2: именования методов с «не» кажется плохой идеей. Скоро вы найдете !notFulfills(!notContains(sdflasdf)). Удача удачи, пытаясь понять, что это делает.