[자료구조 공부 기록] 1. 배열

 

아마 생겼다면 이런 느낌이 아닐까요? Index와 저장공간

특징

• 선형 구조를 가진 자료구조입니다.
• Array를 만들 때부터 길이를 지정하고 만듭니다.
• 같은 자료형들만 넣을 수 있습니다. 
• Index가 존재하여 빠르게 데이터를 찾을 수 있습니다.
• 연속된 메모리 주소에 순차적으로 데이터가 저장됩니다.
• 다차원으로 저장이 가능합니다. 

 

장점 및 단점

 

1) 장점

• 빠른 접근이 가능합니다.
• 비교적 성능이 좋습니다.

연속된 메모리에 저장되있으니 순서만 알고 있다면 빠르게 데이터를 가져올 수 있습니다.

 

 

2) 단점

• 데이터를 추가/삭제 하는 것이 어렵습니다.
• 길이를 바꿀 수 없습니다. (메모리 낭비가 될 수 있다.)

예를 들어 중간에 C 를 삭제해야 된다면..? 길이는 10인데 4만큼만 저장되있다면..?

만약 2번째 원소인 C를 삭제해야 된다면 JAVA와 LISP를 앞으로 1번 index 자리에 넣어줘야 하기 때문에 비효율 적인 삭제가 되는 것입니다. 만약 중간에 삽입을 해야 한다면 그것도 동일하게 원소들을 뒤로 밀어줘야 하겠죠?

 

 

---

아직 다루지는 않았지만 비슷한 자료구조인 List와는 2가지 차이점이 있습니다.

 

1. Array는 index가 존재하지만 List는 존재하지 않는다. (대신 대체할 포인터를 가지고 있다.)
2. Array는 메모리들의 주소가 연속적이지만 List는 불연속적일 수도 있다.

이렇게 들으면 저처럼 Python으로 코딩을 시작하고 배운 사람들은 무언가 이상함을 느끼실텐데요.

 

---

"Python에 List는 index도 있고 연속적인 거 같던데... Python List는 List가 아닌가?"

---

네 맞습니다.

 

Python List는 엄밀히 말하면 여기서 말하는 자료구조의 List와는 차이가 있습니다. 

 

하지만 너무 어렵게 생각 안 하시고 그냥 같은 단어를 썼을 뿐이라고 생각하면 될 듯싶습니다.

 

저 같은 경우에는 Python(CPython) List는 Dynamic Array(동적 배열)을 토대로 배열과 리스트의 장점을 합쳐서 만든 객체라고 보고 있습니다. 

 

Python QnA 참조 : https://docs.python.org/3/faq/design.html#how-are-lists-implemented-in-cpython

 

 

 

 

 

 

언제라도 글에 틀린 점이 있다면 댓글로 남겨주시면 감사하겠습니다.