Каков наиболее эффективный способ обработки дублирующейся записи в связанном списке? - PullRequest
Новая
       31

Каков наиболее эффективный способ обработки дублирующейся записи в связанном списке?

0 голосов
/ 02 июля 2019

Я реализую упорядоченный связанный список, и я хотел бы знать, каков наиболее эффективный способ обработки дублирующейся записи при вызове метода вставки.Лучше искать, если запись уже существует до операции или оценить, существует ли запись уже внутри операции, и выдать исключение?

Метод # 1 

public void insert(int key){
    if(isEmpty())
        head = new Node(key);
    else if(key < head.data){
        /* Code to verify if they are equal */
        /* ... */
        /* ... */
        Node new_node = new Node(key);
        new_node.next = head;
        head = new_node;
    }else{
        Node tmp = head;
        while((head.nex != null) && (key > tmp.key)){
            /* Code to verify if they are equal */
            /* ... */
            /* ... */
            tmp = tmp.next;
        }
        /* Create node and change "pointers"*/
        /* ... */
        /* ... */
    }               
}

Метод № 2 

public void insert(int key){
    if(exists(key)){
        /* Throw an exception */
    }
    /* Code for insert element */
    /* ... */
    /* ... */       
}

1 Ответ

1 голос
/ 02 июля 2019

Поскольку вы спрашиваете об эффективности, всегда будет эффективнее выполнять проверку на наличие дубликатов внутри вашей реализации "вставки". Вот почему предположим, что у вас есть отсортированный связанный список с N элементами. Элемент, который вы пытаетесь вставить, больше, чем любой из элементов, находящихся в данный момент в списке. Если вы выполняете поиск сначала, а затем вставляете, вам придется пройти N элементов, чтобы подтвердить, что элемент отсутствует в списке. Затем вы снова пройдете N элементов, чтобы найти правильное место для вставки вашего нового элемента.

Я бы предложил написать метод "поиска", который возвращает узел с наибольшим ключом, который меньше или равен ключу, который вы ищете. Например, если указан список { 1, 2, 5, 7, 10 } и ключ поиска 6, ваш метод поиска должен вернуть узел 5. Теперь вы можете вызвать search внутри вашего метода вставки, и если он вернет либо узел с ключом, который вы искали, либо узел с наибольшим ключом, который все еще меньше, чем ваш ключ поиска, после чего вы можете вставить новый узел с поиском ключевое значение. Как то так: 

insert(k)
  Node n = search(k) // what should search return if the list is empty?
  if (n.data < k)
     // insert new node after "n"
  else
     // handle existing key

Надеюсь, это поможет!

...