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