배열 (ArrayList)
-
논리적 순서 === 물리적 순서
-
Index 통한 원소접근 용이
-
구현 쉬움
-
리스트 크기 제한
-
삽입, 삭제 등 연산에 대한 Cost가 높음
삽입, 삭제의 경우 순서를 맞추기 위해서 Shift 연산이 필연적이기 때문이다.
연결리스트 (LinkedList)
-
배열의 Cost 높은 비효율성을 극복하고자 등장
-
논리적 순서 !== 물리적 순서
LinkedList는 각 원소가 다음 논리적 Index위치에 해당하는 물리적 주소를 가지고 있다.
따라서, 삽입, 삭제 시, 물리적 주소에 대해 변경만 해주면 된다. -
리스트 크기에 영향 없이 데이터 삽입,삭제 가능
-
원하는 Index를 참조하려면, 1번 Index부터 차례대로 접근해야 해당 Index를 찾을 수 있음.
단일 연결리스트
data와 next(포인터)로 구성된 한방향 연결 리스트
첫 번째 원소에서 시작해야 리스트를 종주 가능
이중 연결리스트
단일 연결리스트의 단점을 극복하고자 등장
next(포인터)외에도 prev(포인터)의 존재 등장
더 많은 메모리 사용
어느 원소에서 시작해도 리스트를 종주 가능
원형 연결리스트
머리나, 꼬리가 존재하지 않음
다음 원소를 가리키는 포인터 레퍼런스에는 반드시 null이 아닌 어떤 원소가 들어감
시작점을 제대로 추적하지 않으면 무한루프 가능성 존재
스택 (Stack)
LIFO (Last In First Out), 마지막에 들어간 것이 가장 먼저 나오는 자료구조
Push, Pop 을 통해 데이터를 삽입,삭제
여러개의 하위 작업으로 나눌 수 있는 작업을 관리할때 유용하게 쓰임
서브루틴에서 사용할 반환 주소, 매개변수, 지역변수 등을 추적
List로 구현하면 객체를 제거해야하는 작업이 필요
Array로 구현하면 삭제할 필요없이 Index를 줄이고 초기화만 하면됨
Array로 구현하는 것이 더 좋음
큐 (Queue)
FIFO (First In First Out), 먼저 들어간 것이 가장 먼저 나오는 자료구조
Array로 구현하면 poll 연산 이후, 객체를 앞당기는 작업 필요
List로 구현하면 객체 1개만 제거 하면 됨
삽입, 삭제 용이한 LinkedList로 구현하는 것이 더 좋음
