02a. 연결 리스트와 배열과 배열리스트

여러 데이터를 저장하는 구조

여러 데이터를 저장하는 자료형은 대표적으로 배열(Array)와 리스트(List)가 있습니다.

배열

여러 데이터를 저장한 자료형 중에 월등히 빨리 접근 할 수 있습니다.
하지만 처음 생성시 얼만큼 사용할 건지 미리 정해야되서, 실제 사용보다 너무 크게 크기를 정하면 메모리 낭비가 됩니다.

또한 배열 크기가 너무 큰 경우 이만큼 할당할 수 있는 메모리 공간을 찾기 힘들 수 있습니다.

배열이 꽉 차면 사이즈 변경이 불가하기 때문에 새로 만들어 복사해줘야합니다.

그 외로 다차원 표현이 가능합니다.(2차원 또는 3차원 배열)

배열 리스트

배열과는 다르게 사이즈 변경이 가능하여 데이터 삽입 및 삭제가 가능합니다.
하지만 구조는 배열처럼 따닥 붙어있어서 너무 크면 메모리 할당이 힘들 수도 있습니다. 또한 따닥 붙어있는데 삽입 삭제는 가능한 구조다보니 다차원을 구현할 수가 없습니다.

연결 리스트

속도는 앞에 나온 것들보다는 느리지만, 삽입 삭제 등의 연산과 다차원 구조가 가능합니다. 또한 필요한 메모리를 띄엄띄엄 둘 수 있어서 메모리 할당의 어려움도 없습니다.(메모리를 전부 다 쓰지않는 이상..)

데이터의 삽입과 삭제 연산이 잦고, 크기의 유동 폭이 큰 경우에는 이 연결리스트를 사용하며, 앞으로 단일 연결 리스트, 이중 연결 리스트, 환형 연결 리스트에 대해 얘기하려 합니다.

 

위키독스 연재 : https://wikidocs.net/book/2868