문서 보기문서 편집수정 내역 리스트(자료구조) (덤프버전으로 되돌리기) [목차] List == 개요 == [[추상적 자료형]], [[자료구조]]의 하나. 순열(Sequence)이라고도 불리며, '''순서'''를 가지고[* '정해진 순서'를 가지기 때문에 선형 구조라고도 하며, 선형구조에는 리스트(List), 스택(Stack), 큐(Queue),데크(Deque)가 있다. 선형 구조가 아닌 것은 비선형 구조로써, 트리(Tree - 흔히 우리가 아는 크리스마스 트리저럼 최상위 점이 아래로 가지를 뻗으며 내려가는 형태),와 그래프(Graph)가 있다.] 일렬로 나열한 원소들의 모임으로 정의한다. 순서가 있다는 점에서 [[집합]]과는 구별되며, 갈림길 없이 일렬로 나열되어 처음과 끝이 각각 하나씩만 있다는 점에서 [[그래프(이산수학)|그래프]]와도 구별된다. 리스트는 보통 다음 연산들을 가지고 있다. * 빈 리스트를 만드는 연산 (Constructor; 생성자) * 리스트가 비어있는지 확인하는 연산 (is Empty?) * 리스트의 앞에 원소를 삽입하는 연산 (add Head 또는 add First) * 리스트의 뒤에 원소를 삽입하는 연산 (add Tail 또는 add Last) * 리스트의 원소를 지우는 연산 (remove) * 리스트의 제일 첫 원소를 알아보는 연산 (peek) * 리스트의 첫 원소를 제외한 나머지 리스트를 알아보는 연산 (peek Next)[* [[연결 리스트]]가 이 연산을 --의도했든 의도치 않았든-- 구현한다.] 리스트를 컴퓨터에서 사용 할 수 있게 구현한 것이 [[연결 리스트]]다. 리스트의 각 원소에 순서대로 번호를 붙일 수도 있으며, 이 번호를 사용해서 임의의 원소를 찾을 수 있는 연산을 추가할 수도 있는데, 때문에 [[배열]]을 리스트의 일종으로 볼 수도 있다. 때때로 [[C언어|C]]같이 자료형 만들기 귀찮은 언어에서 리스트가 필요할 때 그냥 동적할당된 배열 같은 걸로 대충 때우는 경우도 있다.[* 이는 리스트가 '이런 구조다' 라는것만 제시 할 뿐, 그 구조를 어떻게 구현하는지는 신경 쓰지 않기 때문이다. 그렇다보니, 같은 리스트라고 해도 내부 구현이 천차만별일 수 밖에 없다. 이는 가령 리스트에만 국한되지 않고, 큐, 스택 같은 추상적 자료형이 공유하는 특징이다.] 다만 이 경우 필요한 연산만을 구현하는게 장점이자 단점이 될 수 있다. 장점은 필요한 코드만 작성하면 된다는 점과 연산의 제한이 필요한 경우 이를 제어할 수 있다는 점(극단적으로 생성할 때만 데이터를 입력하게 되어있어 get만 허용한다거나... ~~보통 이 경우는 반복자(Iterator)를 쓸텐데...~~)이 있다. 단점으로는 웬만한 실력자가 코드를 작성하지 않은 이상, 버그가 일어날 수 밖에 없는 구조인 점이 있다. 라이브러리를 쓰면 어떤 부분이 약점인지 알 수 있기 때문에 이를 회피하는 코드를 작성할 수 있는데, 직접 작성한 코드의 경우 이런 것이 불가능하기 때문이다. [[LISP]]는 원래 리스트 연산을 위해 탄생했으며, 언어의 모든 곳에서 리스트를 적극적으로 사용함은 물론이고 LISP 프로그램 코드 자체가 곧 리스트 자체이기도 하다. 이렇게 리스트를 적극적으로 쓰기에 리스트에 쓰이는 메모리 관리를 일일이 할 수 없어 [[쓰레기 수집]] 기법을 최초로 사용하기도 했다. 이에 영향을 받은 함수형 언어의 경우 LISP처럼 모든 곳에서 리스트를 활용하지는 않지만, 리스트에 대한 작성이나 관리가 편하게 되어있다. [[Java]]의 경우 대표적인 리스트 계열로 Vector, ArrayList, LinkedList가 있다. Vector의 경우 ArrayList가 생기기 이전에 쓰던 배열 기반의 리스트이고, 최근의 대다수의 책에서도 Vector는 소개하고 있지 않다. 실제로 ArrayList가 대부분의 경우 추천되는데, 쓰레드에 의한 동기화가 필요한 경우에는 ArrayList보다 Vector를 쓰라고 추천하기도 한다.(하지만 그렇다고해도 되도록이면 쓰지 말라고 얘기한다. [[http://stackoverflow.com/questions/11375392/vector-vs-arraylist-which-is-better|StackOverflow의 답변 (2번째) 참고]]) LinkedList의 경우 대부분의 알고리즘과 자료구조에서 배우는 그 [[연결 리스트]](Linked list)가 맞다. 순수한 연결 리스트와의 차이점이라면 peek 연산(메소드)과 pop 연산(메소드)를 이용해 큐(Queue)처럼 이용할 수 있다는 점이 있다. == 관련 문서 == * [[배열]] * [[연결 리스트]] [[분류:자료구조]]캡챠되돌리기