선형 구조 - 배열, 연속 리스트, 연결 리스트

배열(Array)

인덱스를 통해 Value에 접근함.

배열 가운데의 원소가 삭제되면 null 값이 들어감. (밀도≠1)

 

인덱스를 통한 검색시 : O(1)

 

연속 리스트(ArrayList)

배열과 같이 인덱스를 통해 Value에 접근함.

배열 가운데의 원소가 삭제되면 null값이 들어가지 않고 뒤의 원소가 앞으로 땡겨져 채워넣음 (밀도=1)

-> 삽입, 삭제시 원소의 이동이 일어나기 때문에 번거롭다.

연속적으로 놓여있어 검색은 용이하지만 삽입, 삭제시 용이하지 않음.

 

인덱스를 통한 검색시 : O(1)

삽입, 삭제시 : O(n)

 

연결 리스트(LinkedList)

자료들을 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 자료를 연결시킴.

포인터 부분이 필요하기 때문에 기억공간 효율이 좋지 못함.

원소의 이동이 필요 없기때문에 삽입, 삭제시 용이하나 검색시 포인터를 통하기 때문에 접근속도가 느림

 

검색시 : O(n)

삽입, 삭제시 : O(1)