728x90
배열이란?
- 배열은 특정 크기만큼 메모리 공간에 연속적으로 저장하는 자료구조이다.
- 메모리상에서 연속적으로 저장되어 있는 특징을 갖기 때문에, index로 접근이 용이하다.
- 배열의 크기는 처음 생성할 때 정하며 이후에는 변경할 수 없다.
- 삽입/삭제가 오래걸린다. 왜냐하면 데이터를 추가하려고 하는 자리를 비우고 뒤에 있는 데이터를 한 칸씩 뒤로 밀어야 하기 때문이다.
- 배열 중간의 데이터가 삭제되면, 공간 낭비가 발생한다.
- 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을때 사용한다.
링크드리스트란?
- 링크드리스트는 여러개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이다. 첫번째 노드를 head, 마지막 노드를tail이라고 한다.
- 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다. 이 포인터를 통해 자신의 앞에 있는 데이터와 뒤에 있는데이터에 대한 주소를 기억하고 있다.
- 배열과 다르게 메모리를 연속적으로 사용하지 않는다.
- 배열과 다르게 순차적으로 접근해야 한다. 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다.
- 삽입, 삭제가 용이한 이유는 A - B - C 와 같이 연결 리스트에 저장되어 있다고 했을때, B와 C 사이에 Z를 추가한다고 하면 B에서 C를 가리키는 주소를 Z로 변경하고 C에서 B를 가리키는 주소를 Z로 변경하면 되기 때문이다. 또한 Z를 다시 삭제한다고 해도 B가 C를, C가 B를 가리키도록 하면 된다. 따라서 데이터 추가 및 삭제는 O(1)로 가능하다.
- 임의 접근이 불가능하여 처음부터 탐색을 진행해야 한다. O(n)
- 삽입, 삭제 연산이 잦고, 검색 빈도가 적을 때 사용한다.
배열과 링크드 리스트
배열과 링크드 리스트
velog.io
[자료 구조] 배열 & 연결 리스트 (Array & LinkedList)
배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다.메모리 상에서 연속적으로 저장되어 있는 특징을 갖기 째문에, index를 통한 접근이 용이하다.배열의 크기는
velog.io
'Practice > Java' 카테고리의 다른 글
| 테스트코드 공부 참고자료 블로그 (0) | 2023.03.06 |
|---|---|
| 테스트코드 공부 1 (0) | 2023.03.06 |
| 스프링) 의존성 주입 (0) | 2023.02.16 |
| 스프링) JPA 페이징 처리 개념 및 활용방법. (0) | 2023.02.15 |
| 스프링) 빌더 패턴 (1) | 2023.01.17 |