[JAVA] 23. List 컬렉션 클래스 - Stack / LinkedList

List 인터페이스 : 순서가 있는 데이터들의 집합으로 데이터의 중복을 허용합니다. 

(Vector, ArrayList, LinkedList, Stack, Queue(Stack의 반대))

 

 

 

Stack(스택) 

스택의 구조는 선형 메모리 공간에 데이터를 저장하면서 후입선출(LIFO)의 시멘틱을 따르는 자료구조입니다.

 

 

예시 1)

▼▼▼

 

예시 2)

▼▼▼

 

▼▼▼

▼▼▼

▼▼▼

 

 

 

LinkedList 

LinkedList는 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있는 저장 형태입니다.
ArrayList와 같이 데이터의 추가, 삭제 시 불필요한 데이터의 복사가 없어 데이터의 추가, 삭제 시에 유리한 반면 데이터의 검색 시에는 처음부터 노드를 순회해야 하기 때문에 성능상 불리합니다.

 

- 단일 연결 리스트 : 요소의 저장과 삭제 작업이 다음 요소를 가리키는 참조만 변경되므로 아주 빠르게 처리할 수 있습니다.
하지만, 단일 연결 리스트는 현재 요소에서 이전 요소로 접근하기가 매우 어렵습니다.

[next] [next] [next] [next]
데이터  데이터   데이터  데이터

- 이중 연결 리스트 : 현재 요소에서 다음 요소, 이 전요 소를 가지고 있습니다. 따라서
단일 연결 리스트보다 이전 요소로 접근하기가 쉽습니다.

[next] [next] [next] [next] ->정방향
데이터  데이터   데이터  데이터
[pre]  [pre]  [pre]  [pre] <-역방향

 

 

예시 )

▼▼▼

▼▼▼

▼▼▼

▼▼▼