[CS 스터디 발표] 자료구조(Data Structure) - 1

자료구조

자료구조는 전산학에서 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 올바른 선택의 자료구조는 보다 효율적인 알고리즘을 사용할 수 있도록 한다.

 

선형과 비선형

선형 자료구조 : Data요소가 순차적으로 저장되어있는 자료구조

비선형 자료구조 : Tree나 Graph 처럼 멀티 레벨로 구성되어 있고 데이터 요소가 순차적으로 저장되어있지 않는 것.

 

배열(Array)

배열은 메모리에 데이터를  연속적으로 저장하는 자료구조. 인덱스로 조회할 수 있기에 Random Access가 가능함.

하지만 삽입과 삭제시에  앞 요소들을 이동해야하기 때문에 더 많은 비용이 발생

 

단순 연결리스트(Singly Linked List)

단순 연결리스트는 노드에 다음 노드의 주소를 가리키는 정보만 추가되어있는 가장 단순한 형태의 연결리스트.

 

이중 연결리스트(Doubly Linked List)

이중 연결리스트는 다음 노드뿐만 아니라 이전 노드의 주소도 추가되어 있는 연결리스트.

⭐⭐⭐ Array vs ArrayList vs LinkedList

1. Array vs ArrayList

 

Array는 고정적으로 메모리 공간을 할당해서 사용하는 자료구조다. 선언할 때 크기와 데이터 타입을 지정해야해서 삽입 삭제에 매우 비효율적이다. 이를 해결하기 위해 나온 것이 List.

 

ArrayList에서는 크기가 정해지지 않았기에 중간에 데이터를 추가하거나 삭제할 때 Array에서 갖고있는 문제점을 해결할 수 있다. 하지만 중간에 데이터 추가 및 삭제할 때 시간이 오래걸리는 단점이 존재한다.

 

- "자바 기준" 차이점 5가지

1. Array는 고정된 크기, ArrayList는 동적인 배열

2. Array는 Primitive Type과 Object를 모두 담지만, ArrayList는 Object만 담을 수 있다.

3. Array는 제네릭을 사용할 수 없지만, ArrayList는 제네릭을 사용할 수 있다.

4. 길이에 대해 배열은 length, ArrayList는 size

5. 배열은 할당연산자를 사용하고 ArrayList는 add를 사용한다.

 

- ArrayList 삽입/삭제 과정

2. ArrayList vs LinkedList

Linked List와 ArrayList의 차이는 삽입/삭제와 검색의 차이로 볼 수 있다.

- 검색 : ArrayList가 Index로 찾기 때문에 훨씬 빠름(Linked List는 순차접근)

- 삽입/삭제 : LinkedList는 뒤로 밀거나 채우는 작업 없이 주소만 연결해주면 되서 훨씬 빠름.

 

---

참고자료 

https://www.nextree.co.kr/p6506/

자료구조: Linked List 대 ArrayList

https://gyoogle.dev/blog/computer-science/data-structure/Array%20vs%20ArrayList%20vs%20LinkedList.html

Array vs ArrayList vs LinkedList | 👨🏻‍💻 Tech Interview

https://github.com/m1nnh/tech-interview-QnA/tree/master/data-structure

GitHub - m1nnh/tech-interview-QnA: 📋 Preparing for the Interview