[Linked list] 리스트 결합과 데이터 중복 삭제

결합(Union)

1. 두 개의 리스트를 생성한다.

    SinglyLinkedListUnion<Integer> listA = new SinglyLinkedListUnion<>();
    SinglyLinkedListUnion<Integer> listB = new SinglyLinkedListUnion<>();

2. 두 개의 리스트에 데이터를 삽입한다.

    for(int i=0; i<20; i+=2){
        listA.insertNodeHead(i);
    }

    for(int i=0; i<40; i+=4){
        listB.insertNodeHead(i);
    }

3. 두 개의 리스트를 결합한다.

    unionList((SinglyLinkedListUnion<T>) listA, (SinglyLinkedListUnion<T>) listB);

    public void unionList(SinglyLinkedListUnion<T> listA, SinglyLinkedListUnion<T> listB){
        SinglyLinkedListUnion<T>.Node nodeA = listA.headNode;
        while (nodeA.nextNode != null) {
              nodeA = nodeA.nextNode;
        }
        nodeA.nextNode = listB.headNode;
        listA.removeDuplicateData();    
    }

내용 설명

첫 번째 연결 리스트(listA) 마지막 노드로 이동합니다.

listA 마지막 노드의 nextNode는 두 번째 연결 리스트(listB)의 헤더 노드를 할당합니다.

두 개의 연결 리스트가 이어지면서 listA는 결합된 연결 리스트가 되었습니다.

중복삭제(Remove duplicate)

1. 두 개의 리스트에서 중복된 데이터를 삭제한다.

  public void removeDuplicateData() {
    if (isEmpty()) {
      return;
    }

    Node currentNode = headNode;
    Set<T> setData = new HashSet<>();
    setData.add(currentNode.data);

    while (currentNode.nextNode != null) {
      if (setData.contains(currentNode.nextNode.data)) {
        if (currentNode.nextNode.nextNode != null) {
          currentNode.nextNode = currentNode.nextNode.nextNode;
        } else {
          currentNode.nextNode = null;
        }
      } else {
        setData.add(currentNode.nextNode.data);
        currentNode = currentNode.nextNode;
      }
    }
  }

내용 설명

결합된 연결 리스트(listA)의 노드 데이터를 HashSet을 사용하여 해쉬 테이블에 넣습니다.

삽입 단계에서 데이터가 이미 해쉬 테이블에 존재하는 경우 중복 데이터를 의미합니다.

중복 데이터를 삭제하기 위해선 현재 노드의 nextNode를 다음이 아닌 그 다음 번 노드(currentNode.nextNode.nextNode)를 가리키도록 값을 할당합니다.

만약 데이터가 존재하지 않는 경우를 대비해서 null 체크도 함께 해야 합니다.

연결 리스트의 크기만큼 반복문이 모두 실행되면 중복데이터가 삭제된 연결 리스트가 된 것을 확인할 수 있습니다.