JAVA 자료구조 (리스트) - LinkedList 2 (원소 삽입, 원소 삭제)

연결리스트

2. 연결 리스트의 작업

원소 삽입

연결 리스트에서 중간 노드를 삽입하려면 삽입 노드의 바로 앞에 노드, 즉 직전 노드를 가리키는 레퍼런스preNode가 있어야 한다. [그림 5-15]의 예를 살펴보자 (a)와 같이 연결 리스트에서 원소 17과  35 사이에 원소 25를 삽입하려면 레퍼런스 preNode가 원소 25를 담고 있는 노드를 가리키도록 준비한다. 그런 다음 (b)와 같이 원소 17과 35노드 사이에 원소 25의 새 노드를 삽입한다.

 

이 작업을 위한 알고리즘은 다음과 같다. x는 삽입할 원소다.

newNode.item = x
newNode.next = preNode.next
prevNode.next = newNode
numItems++

 

여기서 prevNode.next는 원소 35의 노드를 가리킨다.

 

그림 5- 16 연결 리스트의 맨 뒤에 원소(60)를 삽입하는 예

 

[그림 5-16]과 같이 연결 리스트의 맨 뒤에 노드를 삽일할 때고 앞의  코드는 그대로 작동한다.

 

그림 5-17 연결 리스트의 맨 앞에 원소(5)를 삽입하는 예

 

[그림 5-17]과 같이 연결 리스트의 맨 앞에 노드를 삽입할 경우에는 앞에 제시한 코드는 사용할 수 없다. 이때는 직전 노드가 없어 prevNode.next와 같은 표현을 쓸 수 없기 때문이다.

 

다음은 연결 리스트의 맨 앞에 우너소를 삽입하기 위한 알고리즘이다.  prevNode.next 값을 수정하는 대신 head값을 수정한다.

newNode.item = x
newNode.next = head
head = newNode
numItems++

 

 

알고리즘 5-9 연결 리스트에 원소 x삽입하

if(k=0){
    newNode.item = x
    newNode.next = head
    head = newNode
    numItems++
 }else{
    newNode.item = x
    newNode.next = prevNode.next
    prevNode.next = newNode
    numItems++
}

 

원소 삽입 위치에 다른 삽입 알고리즘은 최종적으로 [알고리즘 5-9]와 같다. 원소를 중간과 맨 끝에 삽입하는 경우와 맨 앞에 삽입하는 경우 두 가지로 나우어 처리한다. 여기서 변수 k는 k번째 원소로서 x를 삽입합을 뜻한다.

 

원소를 삽입할 때 두 가지 경우로 나누지 않아도 되는 방법이 있다. 리스트의 맨 앞에 더미 헤드 노드를 하나 두면된다. 

 

더미(dummy)헤드 노드는 원소가 들어 있지 않은 가짜 노드인데 몇 가지 장점이 있다. [그림5-18]의 (a)는 앞에서 예를 든 기본 형태의 연결 리스트([그림 5-13])에서 첫 번째 노드(원소10) 앞에 더미 헤드 노드를 추가한 것이다. (b)는 더미 헤드 노드가 추가된 빈 열결 리스트다. 더미 헤드 노드가 없는 경우에는 레퍼런스 head값이 null이었는데 이번에는 더미 헤드를 가리키고 있다. 

 

[그림 5-19]는 더미 헤드 노드가 있는 연결 리스트에서 맨 앞에 원소 x를 삽입하는 예다. 더미 헤드 노드가 직전 노드가 되어 prevNode.next에 값을 할당할 수 있다. 중간과 맨 뒤에 원소를 삽입할 때는 [그림 5-15]와 [그림 5-16]삽입 방식과 동일하다.

그림 5-19 더미 헤드 노드가 있는 연결리스트에서 맨 앞에 원소를 삽입하는 예

 

더미 헤드 노드가 있으면 삽입하고자 하는 노드 앞에 항상 직전 노드가 존재해 prevNode.next를 사용할 수 있다. 따라서 [알고리즘 5-9]처럼 두 가지 경우로 나누지 않고 [알고리즘 5-10]만으로 충분하다.

 

알고리즘 5-10 연결 리스트에 원소 x 삽입하기(더미 헤드를 두는 대표 버전)

newNode.item = x
newNode.next = preNode.next
preNode.next = newNode
numItems++

 

 

원소 삭제

그림 5-20 연결 리스트에서 원소(35)를 삭제하는 예

 

이번에도 더미 헤드 노드가 없는 기본 버전부터 시작해보자. 연결 리스트의 노드를 삭제하려면 삭제 노드의 직전 노드를 알아야한다. [그림 5-20]은 원소 35를 삭제하는 예다. prevNode가 삭제 노드 다음 노드로 건터 뛰어 링크하도록 만든다.

 

이 작업 수행하기 위한 코드는 다음과 같다. 이렇게 하면 preNode의 링트가 한 노드를 건너 뛴다. 

prevNode.next = prevNode.next.next
numItems--

 

 

그림 5-21 연결 리스트의 마지막 원소를 삭제하는 예

 

직전 노드 다음에 노드가 존재 하지 않으면 prevNode.next.net기 작동하지 않아 에러가 나겠지만 삭제할 노드(prevNode.next)를 찾아놓고 하는 작업이므로 그런 일은 없다.  prevNode.next.next는 삭제 노드의 다음 노드를 가르킨다. [그림 5-21]의 예과 같이 리스트의 맨 뒤에 있는 노드를 삭제할 때도 위 코드를 그대로 쓸수 있다. prevNode.next.next가 null이 되어 위의 코드가 그대로 작동한다.

 

그림 5-22 연결 리스트의 맨 앞쪽 원소를 삭제하는 예

 

하지만 [그림 5-22]와 같이 연결 리스트의 맨 앞에 있는 노드를 삭제할 경우에 앞에 제시한 코드를 쓸 수 없다. 이때는 직전 노드가 없어 preveNode.next와 같은 표현을 쓸 수 없기 때문이다.

 

다음은 연결 리스트의 맨 앞쪽 원소를  삭제하기 위한 코드다.

head = head.next
numItems--

 

삭제 원소의 위치에 따른 삭제 알고리즘은 최종적으로 [알고리즘 5-11]과 같다. 중간과 맨 끝 원소를 삭제하는 경우와 맨 앞 원소를 삭제하는 경우 두 가지로 나누어 처리한다. 여기서 변수 k는 k번째 원소로서 x를 삭제함을 뜻한다.

 

 

알고리즘 5-11 연결리스트에서 원소 삭제하기

if(k = 0){
    head = head.next
    numItems--
}else{
    prevNode.next = prevNode.next.next
    numItems--
}

 

연결 리스트의 원소를 삭제할 때도 원소를 삽입할 때와 마찬가지로 더미 헤드 노드가 있으면 [알고리즘 5-12]와 같이 두 가지 경우로 나누지 않고 코딩할 수 있다.

 

알고리즘 5-12 리스트의 원소 삭제하기(더미 헤드를 두는 대표 버전)

prevNode.next = prevNode.next.next
numItems--

 

그림 5-23 더미 헤드 노드가 있는 연결 리스트의 세가지 삭제 예

 

[그림 5-23]은 더미 헤드 노드가 있는 연결 리스트에서 맨 앞, 중간, 맨 끝에 있는 원소를 각각 삭제하는 예다.

 

 

 

[출처 - 쉽게 배우는 자료구조 with 자바,  저 문병로]
https://www.hanbit.co.kr/store/books/look.php?p_code=B7033044159

IT CookBook, 쉽게 배우는 자료구조 with 자바