배열과 리스트

📌 배열

 

크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형

 

🔎 장/단점

 

✔ 장점

 

• 메모리에 연속적으로 할당되어 있어 어느 위치에서나 O(1)에 조회가 가능(검색 성능 우수)
• 인덱스를 이용하여 무작위 접근 가능(순차 접근을 하지 않아도 됨)
• 순차 접근을 하더라도 연결 리스트보다 빠름

 

✔ 단점

 

• 자료의 삽입이나 삭제 작업에서 데이터 이동이 많아 비효율적임
• 크기가 고정되어 있어 메모리 낭비나 부족 현상이 발생할 가능성이 높음

 

Reference:

https://hyoeun-log.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-7%EC%9E%A5-%EB%B0%B0%EC%97%B4

[자료구조] 배열 (array)

 

출처: 자바의 정석 by 남궁민

📌 동적 배열

 

동적 배열은 크기가 고정된 배열에서 예상보다 많은 자료가 들어올 경우, 동적으로 크기를 조정할 수 있는 배열의 단점을 보완한 자료형

 

🔎 동적 배열 자료형

 

자바의 ArrayList는 동적 배열 자료형이다. 배열 크기를 임의로 변화시킬 수 있고, 타입을 직접 설정할 수 있다. 하지만 배열 크기가 정해진 용량을 다 채우면,
더블링이 발생하여 현재의 2배 크기로 늘리는데 기존 데이터를 모두 복사하여 옮기기 때문에 O(n)의 비용이 발생한다. 입력 시간이나 검색 시간은 O(1)으로 동일하다.

 

Reference:

https://class-programming.tistory.com/56

자바 컬렉션 (Java Collection) 정리

 

📌 연결 리스트

 

데이터의 순서가 메모리에 물리적인 순서로 저장되지 않는 자료구조

 

모든 노드는 연결 구조이며, 데이터와 다음 노드의 주소로 구성되어 있다.

 

🔎 장/단점

 

✔ 장점

 

• 포인터 작업만 하면 되므로, 새로운 노드를 삽입하거나 삭제하기가 간편
• 빈 공간을 허용하지 않기 때문에 데이터 관리에 편리 (자동 정렬)
  • 데이터 개수만큼 메모리를 할당하므로, 메모리 관리가 편리
• 시작 또는 마지막 노드의 삽입/삭제/추출은 O(1)에 가능

 

✔ 단점

 

• 특정 인덱스를 찾기 위해서는 전체 데이터를 순서대로 읽어야 하므로, O(n)의 시간이 소요됨(검색 능력 떨어짐)
• 객체로 데이터를 다루기 때문에 적은 양의 데이터만 쓸 경우 배열에 비해 차지하는 메모리가 큼
  • Wrapper class는 기본 자료형의 객체 자료형을 말한다.
  • int의 경우, Integer라는 wrapper class가 있는데, 플래그, 포인터, 락, 값 등을 저장하기 때문에 16byte가 할당된다.

 

🔎 구현

 

Reference:

https://freestrokes.tistory.com/84

Java로 연결 리스트(Linked List) 구현하기