Python: Array 구현하기

Python으로 Array 구현하기

class Array:
    def __init__(self, size):
        self.data = [None] * size
        
    def get(self, idx):
        if idx < 0 or idx >= len(self.data):
            raise IndexError("Index out of range")
            
        return self.data[idx]
    
    def set(self, idx, value):
        if idx < 0 or idx >= len(self.data):
            raise IndexError("Index out of range")
        self.data[idx] = value

Array로 Linkedlist 구현하기

class ArrayList:
    def get(self):
        value = self.data.get(self.cur)
        
        return value
        
    def move_next(self):
        check = self.next.get(self.cur)
        if check == None:
            raise Exception("Out of List!")
        #next node가 Noned이면 마지막 노드 리스트의 끝
        self.cur = check
        
    def add(self, value):
				#i는 data j는 next
				#이중 for 문으로 돌아가면서 맞는거 찾기
        size = self.size
        if self.cur == None:
            self.cur = 0
            self.head = 0
            self.tail = 0
            self.data.set(self.cur, value)
            self.next.set(self.cur, None)
        else:
            for i in range(size):
                if self.data.get(i) == None: #빈칸 찾기
                    for j in range(size):
                        if j == self.cur: #새로운 데이터의 위치 이전 데이터 next에 삽입
                            self.next.set(j, i)
                            break
                    
                    self.data.set(i, value)
                    self.next.set(i, self.cur)
										#데이터 바꿔주기
                    if self.cur == self.tail:
                        self.tail = i
                        self.next.set(i, None)
												#마지막 노드일 경우 대처
                    self.cur = i
										#cur 변경
                    break
        
    def delete(self):
        if self.cur == self.head:
            if self.cur == self.tail:
                self.tail = None
                self.head = None
            
            self.data.set(self.cur, None)
            self.head = self.next.get(self.cur)
            self.cur = self.next.get(self.cur)
            #하나의 데이터만 있을 경우 처리

        else:
            for i in range(self.size):
                if self.cur == i: # 현재 위치를 찾고
                    for j in range(self.size):
                        if i == self.next.get(j): #이전 next를 찾아 현재의 next 덮어쓰기
                            self.next.set(j, self.next.get(i))
                            break
                            
                    self.data.set(i, None)
                    self.next.set(i, None)
                    self.cur = j
										#바뀐다음에 마지막 노드인지 확인
                    if self.cur == self.tail:
                        self.tail = i
                    break
        
        
    def move_front(self):
        self.cur = self.head
        
    def __init__(self, size):
        self.size = size
        self.data = Array(size)
        self.next = Array(size)
        self.cur = None
        self.head = None
        self.tail = None

Array로 Stack 구현하기

class ArrayStack:
    def push(self, value):
        if self.array.get(self.size-1) == None:
						#빈칸을 찾아 빈곳에 저장하기
            for i in range(self.size):
                if self.array.get(i) == None:
                    self.array.set(i, value)
                    break
        else:
            raise Exception("Out of Range!")
    
    def pop(self):
        for i in range(self.size-1, -1, -1):
						#뒤부터 빼야하기 때문에 범위가 역으로 올수있게
            if self.array.get(i) != None:
                value = self.array.get(i)
                self.array.set(i, None)
                
                return value
            
        else:
            return None
    
    def __init__(self, size):
        self.size = size
        self.array = Array(size)
				#array라 발생하는 사이즈의 제약

→ 틀리지 않지만 빈칸을 찾기위해 리스트를 다 비교해야함 시간복잡도 O(N)

class ArrayStack:
    def push(self, value):
        if self.top == self.size:
            raise Exception('overflow')
        self.array.set(self.top, value)
        self.top = self.top + 1
    def pop(self):
        if self.top == 0:
            raise Exception('underflow')
				value = self.array.get(self.top)
				self.array.set(self.top, None)
        self.top -= 1
				
        return value
    def __init__(self, size):
        self.size = size
        self.array = Array(size)
        self.top = 0

# [None, None, None] top = 0
# [1, None, None] top = 1
# [1, 2, None] top = 2
# [1, 2, 3] top = 3
# -> overflow
# array.get(top) -> None
# array.get(top-1) -> 3

→ count를 index로 사용하면 해당 인덱스로 바로 접근하기 때문에 시간복잡도 O(1)

Array로 Queue 구현하기

class ArrayQueue:
    def enqueue(self, value):
        if self.array.get(self.size-1) == None:
            for i in range(self.size):
                if self.array.get(i) == None:
                    self.array.set(i, value)
                    break
        else:
            raise Exception("Out of Range!")
    
    def dequeue(self):
				value = self.array.get(0)
				if value == None:
						return None

        for i in range(self.size-1, -1, -1):
						if i == 0:
								break
						elif self.array.get(i) != None:
						    self.array.set(i-1, self.array.get(i)           
        
				return value
            
    def __init__(self, size):
        self.size = size
        self.array = Array(size)

class ArrayQueue:
    def enqueue(self, value):
        if self.top == self.size:
            raise Exception('overflow')
        self.array.set(self.top, value)
        self.top = self.top + 1

    def dequeue(self):
        if self.top == 0:
            raise Exception('underflow')
				value = self.array.get(0)
				for i in range(self.top):
				    self.array.set(i, self.array.get(i+1))
				
				self.array.set(self.top, None)				
        self.top -= 1
			
        return value
    def __init__(self, size):
        self.size = size
        self.array = Array(size)
        self.top = 0