리스트
- 순서를 가진 데이터의 집합을 가리키는 추상자료형
- 동일한 데이터를 가지고 있어도 상관 없다. (원소 중복을 허용함)
- 리스트는 연결 리스트를 의미한다? No! 구현 방법에 따라 크게 두가지로 나뉜다.
- 1) 순차 리스트
- 2) 연결 리스트
순차 리스트
: 배열을 기반으로 구현된 리스트 , 원소 물리적 저장 순서 == 원소 논리적 순서
장점
- 데이터의 참조가 쉽다.(인덱스 값을 기준으로 어디든 한번에 참조 가능하다)
단점
- 배열의 길이가 초기에 결정되어야 한다. (변경 불가능)
* 실제로 사용될 메모리보다 크게 할당하여 메모리의 낭비를 초래할 수 있으며, 반대로 할당된 메모리보다 많은 자료를 사용하여 새롭게 배열을 만들어야 하는 일이 발생할 수 있다. - 자료의 삽입/삭제 과정에서 데이터들의 이동(복사)가 빈번하게 일어난다.
* 원소의 개수가 많고 삽입/삭제가 빈번하게 일어날수록 작업에 소요되는 시간 증가함.
연결 리스트
: 메모리의 동적할당(객체 생성, 동적: heap)을 기반으로 구현된 리스트, 원소의 물리적 저장 순서 ≠ 원소 논리적 순서, 삽입과 삭제가 빈번한 가변적인 리스트를 구현할 때 사용. 노드는 데이터를 저장할 부분과 한 노드에 연결될 노드의 포인터 위치를 가리키는 부분으로 구성되어 있다.
1. 단순 연결 리스트 (Singly Linked List)
- 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가진다.
- 헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킨다.
- Null을 가리키는 노드가 해당 리스트의 마지막 노드이다.
- 이중 연결 리스트 (Doubly Linked List)
- 두개의 링크 필드(prev, next)와 한개의 데이터 필드로 구성됨.
- 양쪽 방향으로 순회할 수 있도록 노드를 연결하였다.
- 뒤에서 앞으로의 탐색이 가능해진다.
- 중간삽입 때, 이전노드를 바로 찾을 수 있다.
- 순회 연산을 줄일 수 있다.
=> 단일은 뒤에 노드만 가리키고, 다중은 앞뒤 노드를 모두 가리키는 차이
장점
- 동적 크기삽입/삭제 용이
- 데이터의 중간에 삽입 및 삭제를 하더라도 전체를 돌지 않아도 이전 값과 다음값이 가르켰던 주소값만 수정하여 연결시켜주면 되기 때문에 빠르게 진행할 수 있다.
단점
-
임의로 액세스를 허용할 수 없음. 즉, 첫 번째 노드부터 순차적으로 요소에 액세스 해야함 (이진 검색 수행 불가능)포인터의 여분의 메모리 공간이 목록의 각 요소에 필요
-
List의 k번째 값을 찾아라에서는 비효율적이다. -
array나 arrayList에서 index를 갖고 있기 때문에 검색이 빠르지만, LinkedList는 처음부터 살펴봐야하므로(순차) 검색에 있어서는 시간이 더 걸린다는 단점이 존재한다.
Java Collection
1. List 인터페이스
순서가 있는 데이터의 집합으로 데이터의 중복을 허용한다.
- LinkedList : 양방향 포인터 구조로 데이터의 삽입, 삭제가 빈번할 경우 데이터의 위치정보만 수정하면 되기에 유용스택, 큐, 양방향 큐 등을 만들기 위한 용도로 쓰인다.
- Vector : 과거에 대용량 처리를 위해 사용했으며, 내부에서 자동으로 동기화처리가 일어나 비교적 성능이 좋지 않고 무거워 잘 쓰이지 않는다.
- ArrayList : 단방향 포인터 구조로 각 데이터에 대한 인덱스를 가지고 있어 조회 기능에 성능이 뛰어나다.
질문
array와 arrayList의 차이점은?
ArrayList와 LinkedList의 차이가 무엇인가요?
Array와 LinkedList의 차이가 무엇인가요?(N사 전화면접)
출처 1. https://medium.com/@audrl1010/linked-list-%EC%99%80-array-%EC%B0%A8%EC%9D%B4%EC%A0%90-4ba873c2e5f5
2. https://devowen.com/285
3. https://velog.io/@dion/difference-between-array-and-list
4. https://www.geeksforgeeks.org/doubly-linked-list/
지우의 블로그