[자료구조] 배열(Array)과 연결리스트(Linked List)의 장단점

배열과 리스트, 모두 데이터를 나열하는 자료구조

배열(Array)

장점

• 배열 내 요소의 주소를 나타내는 ‘인덱스(index)’를 통해 원하는 요소에 접근, 빠르게 검색 가능.

단점

• 선언할 때 크기가 고정되어 메모리가 모자랄 경우 모든 요소를 새로운 메모리로 이동해야함
• 요소를 중간에 삽입하거나 삭제 시 해당 요소 뒤에 있는 요소들의 위치를 이동시켜야 함(비효율적)

연결 리스트(Linked List)

장점

• 데이터 입력시 주소가 순차적이지 않아 요소를 메모리의 어느곳에나 둘 수 있음 (크기가 동적임)
• 인덱스 대신 현재 위치의 이전 및 다음 위치를 기억하는 형태로, 요소 중간에 삽입, 삭제 시 논리적 주소만 바꿔주면 되기 때문에 요소(데이터) 삽입,삭제가 용이

단점

• 요소에 바로 접근이 가능하지 않고 연결되어 있는 링크를 따라가야만 접근이 가능하여 접근속도가 느림

결론 : 모든 원소의 값을 한 번에 읽어야 한다면 연결 리스트, 특정한 원소만 알고 싶으면 배열