문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류:자료 구조]] ==개요== 데이터부와 포인터부로 구성된 데이터를 체인으로 연결한 데이터 구조를 리스트라한다. 리스트의 각 요소를 노드라 한다. 이떄 자기자신의 구조체로의 포인터를 포함하는 구조체를 '자기 참조 구조체'라 한다. 구조체는 필요할 떄 원하는 크기만큼 메모리 영역을 받아야 함으로 [[동적 메모리 할당]]을 이용하여야 한다. == 상세 == == 개요 == [[추상적 자료형]], [[자료구조]]의 하나. 순열(Sequence)이라고도 불리며, '''순서'''를 가지고 일렬로 나열한 원소들의 모임으로 정의한다. 순서가 있다는 점에서 [[집합]]과는 구별되며, 갈림길 없이 일렬로 나열되어 처음과 끝이 각각 하나씩만 있다는 점에서 [[그래프]]와도 구별된다. 리스트는 보통 다음 연산들을 가지고 있다. * 빈 리스트를 만드는 연산 (Constructor; 생성자) * 리스트가 비어있는지 확인하는 연산 (is Empty?) * 리스트의 앞에 원소를 삽입하는 연산 (add Head 또는 add First) * 리스트의 뒤에 원소를 삽입하는 연산 (add Tail 또는 add Last) * 리스트의 제일 첫 원소를 알아보는 연산 (peek) * 리스트의 첫 원소를 제외한 나머지 리스트를 알아보는 연산[* [[연결 리스트]]가 이 연산을 --의도했든 의도치 않았든-- 구현한다. ] 리스트의 각 원소에 순서대로 번호를 붙일 수도 있으며, 이 번호를 사용해서 임의의 원소를 찾을 수 있는 연산을 추가할 수도 있는데, 때문에 [[배열]]을 리스트의 일종으로 볼 수도 있다. 때때로 [[C(프로그래밍 언어)|C]]같이 자료형 만들기 귀찮은 언어에서 리스트가 필요할 때 그냥 동적할당된 배열 같은 걸로 대충 때우는 경우도 있다. 다만 이 경우 필요한 연산만을 구현하는게 장점이자 단점이 될 수 있다. 장점은 필요한 코드만 작성하면 된다는 점과 연산의 제한이 필요한 경우 이를 제어할 수 있다는 점(극단적으로 생성할 때만 데이터를 입력하게 되어있어 get만 허용한다거나... ~~보통 이 경우는 반복자(Iterator)를 쓸텐데...~~)이 있다. 단점으로는 웬만한 실력자가 코드를 작성하지 않은 이상, 버그가 일어날 수 밖에 없는 구조인 점이 있다. 라이브러리를 쓰면 어떤 부분이 약점인지 알 수 있기 때문에 이를 회피하는 코드를 작성할 수 있는데, 직접 작성한 코드의 경우 이런 것이 불가능하기 때문이다. == 리스트의 다양한 형태 == #원형리스트: 선형 리스트의 마지막 포인터가 NULL이 아니고 첫 노드를 가르키는 구조로 되어 있다. 따라서 리스트의 끝이 없다. #이중 연결 리스트: 역방향 포이터가 존재하여 리스트를 거꾸로 탐색할 수 있게 한다. #이중 연결 원형 리스트: 역방향 포이터가 존재하는 원형 리스트이다. 리스트 문서로 돌아갑니다.