Array , Linked List

Array

• 데이터들이 순서대로 쭉 늘어선 배열의 형식

특징

• 논리적 저장 순서와 물리적 저장 순서가 일치한다
• 따라서 index 로 해당 element 에 접근 할 수 있다 (Big-O(1)

장점 

• search에서 random access 가 가능하다
• 찾고자 하는 원소의 인덱스 값을 알고 있으면 해당 원소로 접근 할 수 있다

단점

1. 삭제에서 시간이 더 많이 걸린다

•  해당 원소에 접근하여 작업을 완료한 후에 또 한 한가지의 작업을 추가적으로 수행 O(1) + O(1)
• 배열의 원소 중 어느 원소를 삭제했을때 배열의 연속적인 특징이 깨지게 된다(빈 공간 발생)
• 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift 해야하는 비용이 발생  O(n)
• 즉 Array 자료구조에서 삭제 기능에 대한 시간 복잡도(time complexity) worst case : O(n)

2. 삽입의 과정에서 시간이 더 많이 걸린다

•  첫번째 자리에 새로운 원소를 추가할 경우 모든 원소들의 인덱스를 1씩 shift 해야한다 : O(n)

---

Linked List

• 위에서 언급한 Array의 문제점을 해결하기 위한 자료구조가 Linked List
• 순서대로 늘어선 것이 아니라 자료의 주소 값으로 서로 연결되어 있는 구조

특징

• 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다
• 따라서 이부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1) 만에 해결할수 있다

단점

• 원하는 위치에 삽입을 하고자 할때 원하는 위치를 Search 하는 과정에서 첫번째 원소부터 모두 확인해야함
• Array와 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않는다
• 어떤 원소를 삭제 또는 추가하고자 할때 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생

시간복잡도(time complexity)

• search : O(n)
• 삽입 & 삭제 : O(n)

---

ArrayList vs Listed List

Array List

• LinkedList 는 몇 개의 참조자만 바꿈으로써 새로운 자료의 삽입이나 기존 자료의 삭제를 위치에 관계없이 빠른 시간안에 수행 할 수 있다
• ArrayList는 O(N) 만큼의 연산 속도가 걸리기 때문에 자료의 최대 개수에 영향을 받지만, LinkedList는 제약이 없다
• ListedList 는 무한 개수의 자료를 삽입 할 수 있지만(메모리의 용량 무한정 가정)
• ArrayList는 크기가 한정되어 있기 때문에 결국 포화 상태에 이르게 된다
• ArrayList의 크기를 재조정하는 연산을 수행하여 크기를 늘릴 수도 있지만, 상당한 연산량이 요구된다

---

결론

LisnkedList

• 삽입/식제가 빈번하게 발생하는 프로세스의 경우 LinkedList 를 사용하여 시스템을 구현
• ListedList에서는 순차접근(sequential aceess)만이 가능
• 단순 LinkedList는 단방향성을 갖고 있기 때문에 인덱스를 이용하여 자료를 검색하는 어플리케이션에는 적합 X
• 참조자를 위해 추가적인 메모리를 할당해야 하는 단점
• 자료들의 크기가 작은 리스트의 경우 참조자를 위한 추가적인 메모리 할당은 비실용적

ArrayList

• ArrayList는 사이즈가 고정되어 있기때문에 삽입 시 사이즈를 늘려주는 연산이 추가되어야함
• 삭제시 빈 인덱스를 채워야 하기때문에 채워주는 연산이 추가되어야 함
• 이런 부가적인 연산은 시스템의 성능 저하로 이어져 삽입/삭제 빈번 프로세스에는 치명적

※ 장단점 비교

Linked List의 장점	Linked List의 단점
자료의 삽입과 삭제가 용이	포인터의 사용으로 인해 저장공간의 낭비가 발생
리스트 내에서 자료의 이동은 필요하지 않다	알고리즘 복잡
사용 후 기억 장소의 재사용 가능	특정 자료의 탐색 시간이 많이 소요
연속적인 기억 장소의 할당이 필요하지 않다

 

※ 시간 복잡도(time complexity) 비교

	ArrayList	LinedList
Indexing	O (1)	O (n)
Insert / Delete at begining	O (n)	O (1)
Insert / Delete at end	O (1)	O (n) - Last element unknown O (1) - Last element known
Insert / Delete in middle	O (n)	search time + O (1)
Wasted space ( average )	O (n)	O(n)

 

Reference

1. DataStructure with Java Language 송주석/서성훈 저
2. KOSTA 자료구조