Data structure - Array, Linked Lists

Array

정의 : 연속된 index로 정의된 변수의 sequenced collection

접근 방법

• index 이용 : A[i]
• length 이용 : len(A)

Operations(for Sorted Array)

1. add
   • Sorted된 상태를 유지하며 추가할 index search
   • n-i개의 element를 뒤로 이동하여 추가할 공간 확보
   • add
2. delete
   • A[i] 제거
   • n-i-1 element들을 앞으로 이동(이동해야 하는 element의 숫자를 정확히 알고 있기 때문에 비교할 수 없다.)
   • Time Complexity가 좋지 못하다
3. search

• binary search

4. sorting

import array

class DataArray:
     
    def add(self,element):
        self.arr.add(element)
        return self.arr
        
    def insert(self,index,element):
        self.arr.insert(index,element)
        return self.arr

    def delete(self, element):
        if val in self.arr:
            self.arr.delete(element)
        return self.arr

    def index(self, element):
        return self.arr.index(element)

Sorted, Unsorted

Operation	Sorted Array	Unsorted Array
Search	O(log n)	O(n)
Insertion	O(n)	O(1)
Deletion	O(n)	O(1)
Sorting	O(nlogn)	X

search : Sorted Array 가 더 효과적
add & delete : Unsorted Array 가 더 효과적

Time Compexity

1. Sorted Array
   • Find(Search) : O(logn)(binary search)
   • Add(Insertion) : O(n)
   • Remove(Deletion) : O(n)
2. Unsorted Array
   • Find(Search) : O(n)(linear search)
   • Add(Insertion) : O(1) , array 끝에 추가
   • Remove(Deletion) : O(1) , 지우고 싶은 element를 last element와 바꾸고, last element를 지운다

Binary Search(for Sorted Array)

left = 0
right = n - 1
while left < right:
	mid = (left + right) / 2
	if a[mid] < x:
		left = mid + 1
	else:
		right = mid
if (left == right) and (a[left] == x):
	found = True
	foundpos = left
else:
	found = False