선형 구조
한 원소 뒤에 하나의 원소만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조를 가짐
-> Array , Linked List, Stack, Queue
비선형 구조
원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절함
-> 그래프, 트리
배열(Array)이란?
연관된 데이터를 연속적인 형태로 구성된 구조를 가짐
배열에 포함된 원소는 순서대로 번호(index)가 붙음
특징
고정된 크기를 가지며 일반적으로는 동적으로 크기를 늘릴 수 없음
원하는 원소의 index를 알고 잇다면 O(1) 시간에 찾을 수 있음
단점
특정 index를 삭제하면 빈공간이 생김. 연속적인 특징을 유지하기 위해서 그 뒤의 인덱스 원소들을 shift해줘야 하는 비용이 발생하고 최악의 경우엔 O(n)의 시간복잡도를 가질 수 있음
첫번째 자리나 중간에 원소를 삽입할 경우에도 O(n)의 시간복잡도 가짐
추가와 삭제가 반복되는 로직에서는 권장되지않음. 탐색이 많은 경우에 배열을 사용하는 게 유리
연결리스트(linked List)란?
추가, 삭제가 반복되는 로직에 비효율적인 배열의 문제점을 해결하기 위한 자료구조가 Linked List임.
각 요소를 포인터로 연결하여 관리하는 선형 자료구조. 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 나뉨. 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있음.
특징
메모리가 허용하는 한 요소를 제한 없이 추가할 수 있음
탐색은 O(n)이 소요됨
요소를 추가하거나 제거할 때는 O(1)이 소요됨
단점
논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문에 어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해 O(n)이 추가 발생
Linked List는 Tree구조의 근간이 되는 자료구조이며, Tree에서 사용되었을 때 그 유용성이 드러남
연결 리스트 종류
단일 연결 리스트, 이중 연결 리스트, 환형 연결 리스트
단방향, 양방향, 원형
Array의 가장 큰 특징과 그로 인해 발생하는 장단점을 설명해보세요.
배열의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점임. 데이터에 순서가 있기 때문에 0부터 시작하는 index가 존재하며, index를 사용해 특정 요소를 찾고 조작이 가능하다는 것이 배열의 장점임
순차적으로 존재하는 데이터의 중간에 요소가 삽입되거나 삭제되는 경우 그 뒤의 모든 요소들이 한 칸식 뒤로 밀리거나 당겨줘야 하는 단점이 존재. 그래서 추가와 삭제가 반복되는 로직보다는 탐색이 많은 경우에 배열을 사용하는 것이 좋음
Array와 Linked List의 차이가 무엇인가요?
특정 인덱스에 접근할때 그리고 요소를 삽입하거나 삭제할 때 방법과 시간복잡도에서 차이를 보인다.
특정 요쇼에 접근할때 Array는 직접 접근하여 시간복잡도가 O(1)인 반면, Linked List는 순차적으로 검색하며 찾아야해서 시간복잡도가 O(n)이다.
삽입,삭제를 할 경우 배열에서는 요소들은 인접한 메모리 위치에 연이어 저장이 되고, Linked List는 새로운 요소에 할당된 메모리 위치 주소가 Linked List의 이전 요소에 저장된다. 배열에서는 O(n)이 소요되지만, Linked List에서는 O(1)이 소요됨
메모리 할당에서도 차이를 보인다. 배열에서 메모리는 선언 시 컴파일 타임에 할당이 되고 Stack 영역에 할당이 이루어지는 반면, Linked List는 새로운 요소가 추가될 때 런타임에 메모리를 할당하고, Heap 영역에 할당이 이루어짐.
Array와 ArrayList의 차이점은?
둘은 모든 것이 비슷함. 가장 큰 차이점은 길이를 조정할 수 있는가,없는가임
Array는 고정길이라 계속 데이터가 늘어날 때, 최대 사이즈를 알 수 없을 때는 사용하기 부적합하고 중간에 데이터 삽입하거나 삭제할 때도 비효율적임. 반면 ArrayList는 가변길이임. 동적이고 크기 조정이 가능한 동적 배열 구조임. 많은 편의성을 제공하지만 크기 조정과 메모리 관리 등에서 약간의 성능 저하가 발생할 수 있음.
🫠
출처: https://alreadyusedadress.tistory.com/326
https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%A9%B4%EC%A0%91%EC%A7%88%EB%AC%B8-%EB%AA%A8%EC%9D%8C
