순서리스트의 연결표현(2)

(2) current 변수가 NULL인 경우

이 경우는 추가원소의 직전노드가 없는 경우로, 추가노드는 연결리스트의 첫 번째 노드로 추가된다.

 

추가원소가 연결리스트의 첫 번째 노드가 된다면, 연결리스트의 첫 번째 노드를 나타내는 노드포인터(예를 들면, first)를 변경해야 하는데, 이것은 current 노드의 직후노드로 추가할 때 추가노드를 current 노드의 링크에 연결하는 대신 첫 번째 노드포인터 변수 first에 연결하는것과 같게 된다.

 

추가원소 x를 연결리스트의 첫 번째 노드로 추가할 때는 추가원소를 위한 노드를 생성한 후(temp 노드), 순차적으로 first 노드(노드포인터 first가 나타내는 노드)를 temp 노드의 링크에 연결하고, 노드포인터 first가 temp 노드를 나타내도록 하면 된다.

 

연결리스트의 삭제연산

연결리스트에서 어떤 노드를 삭제하면, 그 직전 노드의 링크가 삭제노드의 직후노드를 나타내도록 변경하고, 삭제노드의 메모리를 해제하면 된다.

 

삭제노드를 나타내는 노드포인터 변수를 temp라고 하고 삭제한 노드의 직전 노드를 나타내는 노드포인터 변수를 current 라고 하면, 삭제연산은 다음의 두 경우로 구분해서 고려할 수 있다.

 

(1) current가 NULL이 아닌 경우

이 경우는 삭제할 노드인 temp 노드가 current 노드의 직후노드인 경우로, 삭제노드 temp는 연결리스트에서 삭제된다.

 

연결리스트의 관점에서 보면, current 노드의 링크에 삭제노드의 직후노드를 연결하면, 삭제노드는 연결리스트에서는 논리적으로 삭제되어 접근할 수 없게 되지만, 일반적으로 삭제노드의 원소값(자료필드 값)은 연결리스트에서는 삭제되더라도 프로그램의 다른 부분에서 사용될 수 있고,

또 삭제 노드의 메모리는 동적변수로 할당받은 것이므로 더 이상 필요 없으면 해제하여 반환하는 것이 바람직하다.

 

(2) current가 NULL인 경우

이 경우는 삭제노드의 직전노드가 없는 경우로, 연결리스트의 첫 번째 노드가 삭제된다. 연결리스트의 첫 번째 노드를 삭제하면, 연결리스트의 첫 번째 노드를 나타내는 노드포인터(예를 들면, first)를 변경해야 하는데, 이 것은 current 노드의 직후노드를 삭제할 때 삭제노드의 직후노드를 current 노드의 링크에 연결하는 대신 첫 번째 노드포인터 변수 first에 연결하는 것과 같게 된다.

 

연결리스트에서는 임의의 위치에서 노드를 추가 또는 삭제하게 되면, 그 직전노드의 링크만이 영향을 받고, 나머지 노드들은 아무런 영향을 받지 않는다.

 

그래서 순차리스트에서와는 달리 연결리스트에서는 추가 또는 삭제연산을 수행할 때 다른 노드들의 이동이 불필요하기 때문에 추가 및 삭제연산의 발생위치에 관계없이 항상 일정한 시간 내에서 연산을 신속하게 처리할 수 있다.

 

따라서 연결리스트는 원소의 추가와 삭제가 빈번하게 발생하는 환경에서 순서리스트를 유지해야 할 때 순차리스트보다 더 유용할 수 있다.

 

그 외 연결리스트의 처리연산들

- searchLinkedlist(L, key): 연결리스트 L에서 key 값을 포함하는 노드를 탐색해서 반환한다.

- printLinkedlist(L): 연결리스트 L의 모든 노드들의 자료필드값을 순차적으로 출력한다.

- reverseLinkedlist(L): 연결리스트 L의 노드들을 역순으로 연결한다.

 

특히 위 연산들은 모두 연결리스트의 모든 노드들을 순차적으로 접근해 가면서 필요한 처리를 수행하는데, 연결리스트 응용에서는 이와 같은 처리 예들이 많이 있다.

 

Current를 연결리스트 first에서 현재 처리하고 있는 노드를 나타내는 노드포인터라고 하면, 모든 노드들을 순차적으로 접근해 가면서 필요한 처리를 수행하는 프로그래밍 코드는 다음과 같은 형태가 된다.

 

current <- first; While(current<> NULL) {    current 노드를 처리한다;    current <- current->link; }

 

연결리스트는 순차리스트와는 달리 추가연산과 삭제연산을 그 수행 위치에 관계 없이 항상 일정한 시간 내에 수행할 수 있는 장점이 있는 반면에 노드마다 링크를 유지해야 하기 때문에 순차리스트보다는 많은 메모리를 사용하게 된다.

 

또한 연결리스트에서 노드들은 항상 첫 번째 노드부터 순차적으로 접근해야 하기 때문에 연결리스트의 뒤 부분에 있는 노드들에 대한 접근시간은 앞 부분에 있는 노드들보다 느리게 된다.

 

그러나 배열을 이용해서 구현되는 순차리스트에서는 순서에 관계없이 모든 원소들은 일정시간 내에서 신속하게 접근할 수 있다.

 

따라서 연결리스트는 추가와 삭제연산이 비교적 빈번하게 수행되고 모든 노드들을 순차적으로 접근해서 처리해야 하는 응용에서 유용하고, 순차리스트는 추가와 삭제연산이 빈번하지 않고 각 노드들을 독립적으로 접근해서 처리하는 응용에서 유용하게 된다.