LinkedList - 직접 구현하는 연결 리스트2 - 추가와 삭제 1

특정 위치에 있는 데이터를 추가하고, 삭제하는 기능을 만들어보자.

void add(int index, Object e)

• 특정 위치에 데이터를 추가한다.
• 내부에서 노드도 함께 추가된다.

Object remove(int index)

• 특정 위치에 있는 데이터를 제거한다. 
• 내부에서 노드도 함께 제거된다.

 

기능을 구현하기 전에 먼저 어떤 식으로 구현해야 할지 알아보자.

 

첫 번째 위치에 데이터 추가

노드에 다음과 같은 데이터가 있다고 가정해보자.

[a->b->c]

 

첫번째 항목에 "d"를 추가해서 [d->a->b->c] 로 만드는 코드를 분석해보자.

 

1.신규 노드 생성

신규 노드 생성

 

2.신규 노드와 다음 노드 연결

신규 노드와 다음 노드 연결

3. first에 신규 노드 연결

first에 신규 노드 연결

최종 결과

최종 결과

• 노드를 추가했으므로 오른쪽 노드의 index가 하나씩 뒤로 밀려난다.
  • 연결 리스트는 배열처럼 실제 index가 존재하는 것이 아니다. 처음으로 연결된 노드를 inedx 0, 그 다음으로 연결된 노드를 index 1로 가정할 뿐이다. 연결 리스트에서 index는 연결된 순서를 뜻한다.
• 배열의 경우 첫 번째 항목에 데이터가 추가되면 모든 데이터를 오른쪽으로 하나씩 밀어야 하지만 연결 리스트는 새로 생성한 노드의 참조만 변경하면 된다. 나머지 노드는 어떤 일이 일어난지도 모른다.
• 연결 리스트의 첫 번째 항목에 값을 추가하는 것은 매우 빠르다. O(1)로 표현할 수 있다.

 

 

첫 번째 위치에 데이터 삭제

첫 번째 항목을 삭제하는 코드를 분석해보자.

[d->a->b->c]로 만들어진 노드를 [a->b->c]로 변경하면 된다.

 

1. 삭제 대상 선택

 

2.first에 삭제 대상의 다음 노드 연결

 

3. 삭제 대상의 데이터 초기화

• 더는 삭제 노드를 참조하는 곳이 없다. 이후 삭제 노드는 gc의 대상이 되어 제거된다.

최종 결과

• 노드를 삭제했으므로 오른쪽 노드의 index가 하나씩 당겨진다.
• 배열의 경우 첫 번째 항목이 삭제되면 모든 데이터를 왼쪽으로 하나씩 밀어야 하지만 연결 리스트는 일부 참조만 변경하면 된다. 남지 노드는 어떤 일이 일어난지도 모른다.
• 연결 리스트의 첫 번째 항목에 값을 삭제하는 것은 매우 빠르다. O(1)로 표현할 수 있다.

 

중간 위치에 데이터 추가

중간 항목에 "e"를 추가하는 코드를 분석해보자.

[a->b->c]로 만들어진 노드의 1번 인덱스 위치에 e를 추가해서 [a->e->b->c]로 변경하면 된다. 참고로 인덱스는 0부터 시작한다.

 

1. 새로운 노드를 생성하고, 노드가 입력될 위치의 직전 노드(prev)를 찾아둔다.

• 여기서 인덱스 1번의 직전 노드(prev)는 인덱스 0번 노드이다.

2. 신규 노드와 다음 노드를 연결한다. 직전 노드(prev)의 다음 노드를 연결하면 된다.

 

3. 직전 노드(prev)에 신규 노드를 연결한다.

 

4. 최종 결과

• 노드를 추가했으므로 추가한 노드 오른쪽에 있는 노드들의 index가 하나씩 뒤로 밀려난다.
• 배열의 경우 첫 번째 항목에 데이터가 추가되면 모든 데이터를 오른쪽으로 하나씩 밀어야 하지만 연결 리스트는 새로 생성한 노드의 참조만 변경하면 된다. 나머지 노드는 어떤 일이 일어난지도 모른다.
• O(n)의 성능이다.
  • 연결 리스트는 인덱스를 사용해서 노드를 추가할 위치를 찾는데 O(n)이 걸린다.
  • 위치를 찾고 노드를 추가하는데는 O(1)이 걸린다.
  • 따라서 둘을 합하면 O(n)이 걸린다.

 

중간 위치에 데이터 삭제

중간 항목을 삭제하는 코드를 분석해보자.

 

1.삭제 대상을 찾는다. 그리고 삭제 대상의 직전 노드(prev)도 찾아둔다.

 

2.직전 노드(prev)의 다음 노드를 삭제 노드의 다음 노드와 연결한다.

3. 삭제 노드의 데이터를 초기화 한다.

 

4. 최종 결과

• 노드를 삭제했으므로 오른쪽 노드의 index가 하나씩 댕겨진다.
• O(n)의 성능이다.
  
  • 연결 리스트에서 인덱스로 삭제할 항목을 찾는데 O(n)이 걸린다.
  • 연결 리스트에서 항목을 삭제하는 것은 매우 빠르다. O(1)로 표현할 수 있다.

 

연결 리스트와 배열 리스트 둘다 중간에 있는 항목을 추가하거나 삭제하는경우 둘 다  O(n)이다.