[Data-Structure] Array, Linked-List

Array : 

배열이라는 뜻의 Array는 가장 기초적인 자료구조 형식으로, 논리적/물리적 저장 위치가 동일하다는 특징을 가지고 있다.

 

접근 (Access) :

위치 정보를 나타내는 인덱스(Index)를 이용하여 해당 원소에 바로 접근이 가능하다.

접근에 대한 시간 복잡도는 O(1)이라는 특성을 가지고 있는데 이는 삽입(Insert)/삭제(Delete)는 다른 결과를 보여준다.

 

삽입(Insert) / 삭제 (Delete) : 

 

[0,1,2,3,4,5,6,7,8,9] 이라는 Array에 '5' 라는 원소에 접근을 하여 삭제를 하게 된다면

[0,1,2,3,4, ,6,7,8,9] 이와 같이 바뀌게 되는데 '4'와 '6' 사이에 어떠한 값이 들어간 것이 아닌 빈 공간이 생겨버리게 된다.

 

Array의 특성 상 빈 공간이 없도록 연속적이게 유지시킬려면 ( [0,1,2,3,4,6,7,8,9] 처럼 빈 공간이 없도록)

인덱스가 큰 원소들을 한 칸씩 앞으로 당겨줘야되고 그로 인해 시간 복잡도는 접근과 다르게 O(n)이라는 값을 가지게 된다.

 

삭제는 O(n)의 시간이 걸리는 것처럼 삽입 또한 같다.

 

원소를 넣어주려는 위치에 빈 공간을 만들고 넣어야 되기 때문에 인덱스를 한 칸씩 뒤로 밀어내야 되는 것이고 이 또한

O(n)의 시간 복잡도를 가지게 된다.

---

Linked-List :

Linked-List는 Array와는 다르게 논리적 저장 위치와 물리적 저장 위치가 다르다.

이름에서 유추할 수 있듯 List 안의 원소들이 서로 연결된 형식을 띄고 있고 메모리에 저장된 위치를 나타내는 값이 앞 뒤로 연결되어 있다.

 

[0,1,2,3,4,5,6,7,8,9] 라는 배열이 있을 때 Linked-List로 보면 다음과 같은 예시를 들 수 있다.

'1' 이라는 원소의 앞에는 '0'이라는 원소가 있고 뒤에는 '2'라는 원소가 있는데 이를 이용하여 위치를 기억한다.

논리적으로 '1'이라는 원소의 위치가 '0'이라는 원소 뒤에 있다는 것과 '2'라는 원소의 앞에 있다는 것으로 나타내는 것이다.

 

이를 통하여 삭제 또는 삽입을 하였을 때 Index의 Shift는 생기지 않는다.

'1' 원소를 삭제하게 되거나 해당 위치에 다른 원소를 넣게되면 앞 뒤의 메모리 저장 위치 값만 조정하면 끝이기 때문이다.

 

Linked-List는 항상 O(1)이라는 시간복잡도를 가질 수 있을 것 같지만 그렇지는 않다.

배열의 첫 번째 또는 마지막 원소의 삽입/삭제를 실행할 때를 제외하고 Linked-List 역시 O(n)이라는 시간복잡도를 가진다.

이는 논리적/물리적 저장 위치가 다르기에 특정 원소를 찾을 때 처음부터 하나하나 찾기 때문에 O(n)이라는 시간 복잡도를 가지게 되는 것이다.

 

하지만 삭제/삽입의 측면에서는 Linked-List가 일반 Array에 비하여 시간적으로 효율적인것은 사실이다.

---

Conclusion :

Index에 접근을 주로 하는 작업을 할 때는 시간복잡도 상 Array를 이용하는 것이 효율적일 것이고 삽입 또는 삭제가 잦은 작업을 할 때는 Linked-List를 활용하는 것이 효율적일 것이다.