리스트

개요

데이터부와 포인터부로 구성된 데이터를 체인으로 연결한 데이터 구조를 리스트라한다. 리스트의 각 요소를 노드라 한다. 이떄 자기자신의 구조체로의 포인터를 포함하는 구조체를 '자기 참조 구조체'라 한다. 구조체는 필요할 떄 원하는 크기만큼 메모리 영역을 받아야 함으로 동적 메모리 할당을 이용하여야 한다.

개요

추상적 자료형, 자료구조의 하나. 순열(Sequence)이라고도 불리며, 순서를 가지고 일렬로 나열한 원소들의 모임으로 정의한다. 순서가 있다는 점에서 집합과는 구별되며, 갈림길 없이 일렬로 나열되어 처음과 끝이 각각 하나씩만 있다는 점에서 그래프와도 구별된다.

리스트는 보통 다음 연산들을 가지고 있다.

* 빈 리스트를 만드는 연산 (Constructor; 생성자)
* 리스트가 비어있는지 확인하는 연산 (is Empty?)
* 리스트의 앞에 원소를 삽입하는 연산 (add Head 또는 add First)
* 리스트의 뒤에 원소를 삽입하는 연산 (add Tail 또는 add Last)
* 리스트의 제일 첫 원소를 알아보는 연산 (peek)
* 리스트의 첫 원소를 제외한 나머지 리스트를 알아보는 연산[* 연결 리스트가 이 연산을 --의도했든 의도치 않았든-- 구현한다. ]

리스트의 각 원소에 순서대로 번호를 붙일 수도 있으며, 이 번호를 사용해서 임의의 원소를 찾을 수 있는 연산을 추가할 수도 있는데, 때문에 배열을 리스트의 일종으로 볼 수도 있다. 때때로 C같이 자료형 만들기 귀찮은 언어에서 리스트가 필요할 때 그냥 동적할당된 배열 같은 걸로 대충 때우는 경우도 있다. 다만 이 경우 필요한 연산만을 구현하는게 장점이자 단점이 될 수 있다. 장점은 필요한 코드만 작성하면 된다는 점과 연산의 제한이 필요한 경우 이를 제어할 수 있다는 점(극단적으로 생성할 때만 데이터를 입력하게 되어있어 get만 허용한다거나... ~~보통 이 경우는 반복자(Iterator)를 쓸텐데...~~)이 있다. 단점으로는 웬만한 실력자가 코드를 작성하지 않은 이상, 버그가 일어날 수 밖에 없는 구조인 점이 있다. 라이브러리를 쓰면 어떤 부분이 약점인지 알 수 있기 때문에 이를 회피하는 코드를 작성할 수 있는데, 직접 작성한 코드의 경우 이런 것이 불가능하기 때문이다.

리스트의 다양한 형태

1. 원형리스트: 선형 리스트의 마지막 포인터가 NULL이 아니고 첫 노드를 가르키는 구조로 되어 있다. 따라서 리스트의 끝이 없다.
2. 이중 연결 리스트: 역방향 포이터가 존재하여 리스트를 거꾸로 탐색할 수 있게 한다.
3. 이중 연결 원형 리스트: 역방향 포이터가 존재하는 원형 리스트이다.