Array 와 Linked-List 차이

Array

- 정해진 크기 만큼 연속된 메모리 공간을 할당하여 데이터를 저장

- 앞 주소만 알면 다음 주소를 알 수 있음

- index 으로 접근 가능

- 한번 정해진 크기는 변경 불가

- 탐색하기 좋음

- 삭제하는데 시간걸림

배열의 형태

 

Linked-List

- 여러개의 노드들이 순차적으로 연결되어 있는 구조

- 노드 맨 앞 : Head, 노드 맨 뒤 : Tail

- 각 연결되어 있는 노드는 가르키는 노드를 가르키는 포인터로 연결

- 배열과 다르게 연속적으로 할당이 아님

- 탐색하는데 시간 걸림

- 삭제 쉬움 ( 처음, 끝인 경우 )

- 중간이면 탐색해야하 한다는 부분이 존재

 

링크드 리스트의 형태

 

	Array	Linked-List
탐색	O(1)	O(n)
삭제	O(n)	O(1)

배열은 탐색할때, 인덱스 값을 알기 때문에 바로 접근이 가능하지만 삭제 하는 경우에는 그 값을 찾아서 삭제를 하고 나머지 값을 움직여놔야하기 때문에 오래걸립니다. ( 단, 처음과 끝은 O(1) )

 

반대로 링크드 리스트는 연결이 되어있기때문에 계속 따라가서 그 값을 찾아야하지만, 삭제 혹은 삭제는 처음 과 끝일 경우에는 바로 확인이 가능하니 쉽지만, 중간에 있는 부분은 그 값을 찾는데 일일이 확인해야하기 때문에 시간이 조금 걸립니다.