순서리스트의 순차표현

순서리스트의 순차표현(sequential representation)은 순서리스트를 컴퓨터 메모리에 저장할 때 객체들의 논리순서와 메모리의 실제 저장순서를 일치시키는 것으로, 순차적 사상(sequential mapping) 표현이라고도 하며, 순차표현된 순서리스트를 간단히 순차리스트(sequential list)라고 한다.

 

순차리스트는 일반적으로 배열을 이용해서 구현한다.

원소들의 논리순서를 인덱스로 구성하여 순서리스트를 논리적 배열로 표현하고, 이 인덱스를 프로그래밍 언어에서 제공하는 배열의 인덱스에 순차적으로 대응시켜 메모리에 저장하면 원소들의 논리순서와 메모리 저장순서는 동일하게 된다.

 

공집합인 순차리스트의 생성

순차리스트를 구현하기 위해서는 원소들을 순차적으로 저장하기 위한 메모리 공간인 1차원 배열(예를 들면, 크기 N인 1차원 배열 list)과 이 배열에 저장된 순차리스트의 크기(원소갯수)를 나타내기 위한 변수(예를 들면, 정수형 변수 length)를 정의해야 한다.

그리고 순차리스트를 처음 생성하면 공집합이므로, length 변수는 1로 초기화 된다.

 

순차리스트의 추가 연산

순차리스트에서 새로운 원소를 i번째 순서로 추가하면, i번째 원소와 그 뒤의 원소들은 한 칸씩 뒤로 이동하게 되고, 특히 새로운 원소를 맨 앞쪽에 추가하면, 모든 원소들은 한 칸씩 뒤로 이동하게 된다.

 

순차리스트의 삭제 연산

순차리스트의 i번째 원소를 삭제하면, i번째 이후의 원소들은 한 칸씩 앞으로 이동해야 하고, 특히 0번째 원소를 삭제하면 모든 원소들은 한 칸씩 앞으로 이동해야 한다.

 

추가연산과 삭제연산 외에 앞에서 정의했던 retrieveList(L, i), replaceList(L, i, x)등의 순차리스트 연산들도 간단히 구현할 수 있다. 순차리스트는 각 원소의 논리순서 정보를 별도로 저장하지 않고 저장순서로 나타내지만 모든 원소들을 논리순서에 관계없이 동일한 시간에 신속하게 접근해서 처리할 수 있게 한다.

 

다만, 항상 원소들의 논리순서대로 저장순서를 유지해야 하기 때문에 중간의 원소가 삭제되거나 새로운 원소가 추가되면 그에 따라 많은 원소들이 이동해야 하는 문제점이 있다. 따라서 순차리스트는 원소의 추가나 삭제가 필요없이 처음부터 모든 원소들을 순서리스트로 구성해서 처리하는 응용에서 특히 유용하게 된다.

추가와 삭제연산을 수행할 때 많은 원소들을 이동시켜야 하는 순차리스트의 단점은 순서리스트의 연결표현으로 해결할 수 있다.

 

3.3 순서리스트의 연결표현

순서리스트의 연결표현은 순서리스트를 메모리에 저장할 때 객체들의 논리순서와 메모리 저장순서를 일치시키지 않고도 객체들의 논리순서를 유지시키는 것으로, 순서리스트의 비순차적 사상(nonsequential mapping) 표현이라고도 한다. 그리고 연결 표현된 순서리스트를 간단히 연결리스트(linked list)라고 한다.

 

연결리스트는 순서리스트의 논리순서를 유지하기 위해 각 원소는 직후원소의 위치정보를 포함한다. 연결리스트에서 각 원소를 나타내는 것을 노드라고 한다. 노드는 각 원소의 정보를 포함하는 자료 부분과 직후노드에 대한 위치 정보를 포함하는 링크 부분으로 구성된다.

 

노드의 자료 부분을 자료 필드(data field), 링크 부분을 링크필드(link field) 또는 간단히 링크라고 한다. 일반적으로 자료필드 부분은 여러 자료형의 멤버속성들로 구성될 수 있고, 링크필드는 대개 1~2개로 구성된다.

 

연결리스트에서는 원소를 나타내는 노드들 외에 항상 첫 번째 노드에 대한 노드포인터(예를 들면, list)를 별도로 유지해야 하고, 마지막 노드의 링크는 다음 노드가 없기 때문에 항상 NULL이 된다는 점이다.

 

연결리스트는 순서리스트의 한 구현방법이다. 다음은 연결리스트의 연산이다.

- insertLinkedlist(L, current, x): 연결리스트 L에서 current 노드의 다음 순서로 x 값을 갖는 새로운 노드를 추가한다.

- deleteLinkedlist(L, current): 연결리스트 L에서 current 노드의 직후노드를 삭제한다.

- retrieveLinkedlist(L, i): 연결리스트 L에서 i번째 순서의 노드를 탐색한다.

- replaceLinkedlist(L, current, x): 연결리스트 L에서 current 노드의 자료필드값을 x로 대체한다.

- isEmpty(L): 연결리스트 L이 공집합인지 여부를 판별한다.

- lengthLinkedList(L): 연결리스트 L의 노드개수(원소갯수)를 계산한다.