C++로 쉽게 풀어쓴 자료구조/ 리스트

리스트(List)의 추상 자료형

리스트란

리스트 (또는 선형 리스트)는 항목들이 차례로 정리된 선형 자료구조를 의미한다. 순서가 있기 때문에 리스트는 집합과 다르다.

리스트는 스택이나 큐와 달리 중간에 데이터를 삽입하거나 삭제할 수 있다. 대신 그만큼 구현시에 고려해야 할 점들도 많다.

리스트의 추상 자료형

  • 객체
    • 임의의 접근 방법을 제공하는 같은 타입의 요소들의 순서 있는 모임
  • 연산
    • insert(pos, item): 리스트의 pos 위치에 새로운 요소 item을 삽입한다.
    • replace(pos, item): 리스트의 pos 위치에 있는 요소를 새로운 요소 item으로 바꾼다.
    • delete(pos): 리스트의 pos 위치에 있는 요소를 삭제한다.
    • getEntry(pos): 리스트의 pos 위치에 있는 요소를 반환한다.
    • isEmpty(): 리스트가 비어 있는지를 검사한다.
    • isFull(): 리스트가 가득차 있는지를 검사한다.
    • find(item): 리스트에 요소 item이 있는지를 검사한다.
    • size(): 리스트 안의 요소의 개수를 반환한다.
    • display(): 리스트 안의 모든 요소들을 출력한다.

리스트는 배열로 만들 수도 있고 연결 리스트로 만들 수도 있다. 배열로 리스트를 만들면 간편하지만, 크기의 제한 문제도 있고 항목을 중간에 추가 하거나 삭제할 때 요소들의 이동이 발생하기 때문에 성능이 떨어지는 문제도 있기 때문에 대부분의 경우 연결 리스트를 이용하여 리스트를 구현한다.

배열로 구현한 리스트

데이터 멤버

리스트를 가장 간단하게 구현할 수 있는 방법은 배열을 이용하는 것이다. 배열을 이용하여 리스트를 만들 때는 배열의 크기를 나타내는 변수 MAX_LIST_SIZE와 현재 리스트에 저장된 요소의 개수를 나타내는 변수 length가 필요하다.

모든 요소들은 배열의 첫 번째 위치부터 차곡차곡 저장되어야 하고 중간에 비어 있는 항목이 없어야 하는 것이 배열을 이용한 리스트의 기본 가정이다. length 변수는 새로운 요소가 리스트의 맨 뒤에 추가될 때 삽입되어야 하는 위치를 나타낸다. 리스트가 처음 만들어지면 length는 0이 된다.

주요 연산

삽입 연산

리스트 중간에 요소를 삽입하려는 경우, 바로 삽입하면 해당 위치에 있는 다른 요소가 사라지게 되므로, 해당 위치 이후의 모든 요소들을 먼저 뒤로 이동 시킨 후에 삽입하려는 요소를 삽입한다.

삭제 연산

리스트 중간의 요소를 삭제하려는 경우, 해당 위치에 있는 요소를 삭제만 하면 리스트 중간이 비게 되므로, 요소 삭제 후에 해당 위치 이후의 모든 요소들을 앞으로 이동 시킨다.

연결 리스트로 구현된 리스트

연결 리스트로 구현된 리스트

리스트를 배열로 구현할 경우 중간의 요소를 삽입하거나 삭제할 때 비효율적인 자료 이동이 발생한다. 이에 반해 연결 리스트로 리스트를 구현할 경우 링크만 조정해 주면 되므로 이러한 문제가 없다.

삽입 연산

리스트 중간에 요소를 삽입하려는 경우, 해당 위치의 앞의 요소가 삽입하려는 노드를 가리키게하고, 앞의 요소가 가리켰던 노드를 삽입하는 노드가 가리키도록 한다.

삭제 연산

리스트 중간에 요소를 삭제하려는 경우, 해당 위치의 앞의 요소가 삭제하려는 노드가 가리켰던 노드를 가리키도록 한다.

시작 노드 표현 방법: 헤드 포인터와 헤드 노드

배열로 리스트를 구현했던 것과 달리 연결 리스트에서는 시작 노드의 주소만 관리한다.

연결 리스트의 시작 노드는 포인터를 이용한 방법과 노드를 이용한 방법으로 표현할 수 있다. 시작 노드를 포인터로 가리키는 경우 이를 헤드 포인터(head pointer)라고 하는 반면, 시작 노드를 빈 노드를 통해 가리키는 경우 헤드 노드(head node)라고 한다.

헤드 노드는 의미 있는 데이터를 가지지 않으며 단지 삽입, 삭제 코드를 간단하게 할 목적으로 리스트 클래스에 하나의 노드 객체를 선언하여 사용하는 방법이다. 헤드 노드를 이용한 경우 리스트의 실질적인 시작 노드는 헤드 노드의 링크 필드가 가리키는 것이 된다. 고로 헤드 노드를 이용한 방법의 경우 실질적인 헤드 포인터는 헤드 노드의 링크 필드가 담당하게 된다.

다양한 형태의 연결 리스트

원형 연결 리스트

원형 연결 리스트란 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 연결 리스트를 말한다.

원형 연결 리스트의 장점은 한 노드에서 다른 모든 노드로의 접근이 가능하다는 것이다. 원형 연결 리스트가 특히 유용한 경우는 리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적일 수 있다는 것이다. 헤드 포인터가 리스트의 마지막 노드를 가리키는 식으로 연결 리스트를 변형하면 –이 경우 리스트의 첫 번째 노드는 그 다음 노드가 된다– 상수 시간 안에 리스트의 끝에 노드를 삽입할 수 있다.

이중 연결 리스트

이중 연결 리스트는 선행 노드와 후속 노드에 대한 두 개의 링크를 갖는 리스트로 양방향 검색이 가능하다는 이점이 있다. 반면 공간을 많이 차지하고 코드가 복잡해진다는 단점이 있다.

노드 클래스의 삽입과 삭제 연산

이중 연결 리스트에서는 리스트 중간에 삽입이나 삭제가 발생한 경우 선행 노드와 후행 노드를 모두 수정해 줘야 한다.

[ssba]

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기