배열은 가장 기본적인 형태의 자료구조로 구조가 간단하고, 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간이 가장 빠릅니다. 하지만 단점도 있다.
1. 크기를 변경할 수 없다.
- 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야한다.
- 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다.
2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
- 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만,
배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 한다.
위와 같은 배열의 단점을 보완하기 위해 나타난 자료구조가 LinkedList이다.
배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어있다.
위 그림을 보면 링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.
데이터 삭제
링크드 리스트에서의 데이터 삭제는 간단함.
위 그림을 보면 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다.
즉, 하나의 참조만 변경하면 삭제가 이루어진다.
배열처럼 데이터를 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다.
데이터 추가
새로운 데이터를 추가 할 경우
1) 새로운 요소를 생성
2) 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경
3) 새로운 요소가 그 다음 요소를 참조하도록 변경
따라서 위의 데이터 삭제와 같이 데이터 추가도 처리 속도가 빠르다.
하지만 위의 장점도 있지만 단점도 존재한다.
단점으로는 데이터의 접근성이 나쁘다.
이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대하 접근은 어렵다.
예시 ) 연결 리스트에 5개의 노드가 있다고 가정하면 세 번째 노드에 접근하려면 첫 번째 노드 부터 차례대로 찾아가야 한다.
배열처럼 한 번에 갈 수 없다.
이러한 링크드 리스트의 단점을 보완한 것이 더블 링크드 리스트 (이중 연결리스트)이다.
이중 연결 리스트 (Doubly Linked List)
- 단일 연결 리스트의 접근성을 향상 시킨 것이 이중 연결 리스트이다.
- 이중 연결 리스트는 참조 변수를 하나 더 추가하여 다음 요소에 대한 참조 뿐만 아니라 이전 요소에 대한 참조가 가능하다.
이중 원형 연결 리스트(Doubly Circular Linked List)
- 이중 연결 리스트의 접근성을 향상 시킨 것이 이중 원형 연결 리스트이다.
- 이중 연결 리스트의 첫 번째 요소와 마지막 요소를 서로 연결 시킨 것이다.
ArrayList vs LinkedList 성능 비교
| 컬렉션 | 읽기(접근시간) | 추가/삭제 | 비고 |
| ArrayList | 빠르다 | 느리다 | 순차적인 추가삭제는 더 빠름 비효율적인 메모리사용 |
| LinkedList | 느리다 | 빠르다 | 데이터가 많을수록 접근성이 떨어짐 |
* 참고 : 만약 ArrayList의 크기가 충분하지 않으면, 새로운 크기의 ArrayList를 생성하고 데이터를 복사하는 일이 발생하게 되므로 순차적으로 데이터를 추가해도 ArrayList보다 LinkedList가 더 빠를 수 있다.
'프로그래밍 > JAVA' 카테고리의 다른 글
| [JAVA] Properties 란? (0) | 2023.01.31 |
|---|---|
| [JAVA] TreeMap 이란 (0) | 2023.01.29 |
| [JAVA] ArrayList 사용방법 (1) | 2023.01.05 |
| [JAVA] 컬렉션 프레임워크(collection framework) (1) | 2023.01.04 |
| [JAVA] BigInteger , BigDecimal 클래스 (1) | 2022.12.14 |