Array List

# List

리스트란? 선형적인 자료구조로 데이터를 일렬로 늘여 놓은 형태입니다. 일렬로 늘여 놓았기 때문에 순서가 있습니다.

리스트는 Array List와 Linked List로 나뉘며, 연결방식에 따라 Single Linked List와 Double Linked List로 나뉩니다.

 

# ArrayList

array list는 배열 기반의 리스트 이기 때문에 배열과 같은 인덱스를 사용합니다. 이 인덱스를 통한 데이터 접근은 random access방식이기 때문에 리스트에 얼만큼의 데이터가 있던지 간에 인덱스만 알고 있으면 동일한 시간을 소요해서 데이터에 접근할 수 있습니다.

또한, array list는 실제 컴퓨터의 물리적인 공간(메모리공간)에서도 연속적인 공간을 사용하기 떄문에 컴퓨터가 연산하기 쉬운 구조를 가지고 있습니다. 그래서 다음 인덱스로 접근하는 속도가 빠릅니다.

 

# 코드 구현 (python)

class ArrayList:
    def __init__(self, default_size = 5):
        self.size = 0    #데이터갯수(인덱스가 됨)
        self.max_size = default_size  # 배열의 길이(공간)를 지정
        self.list = [None] * self.max_size

 

[ increase size ]

arraylist는 배열의 길이가 정해져야 합니다. 그래서 데이터를 추가하다보면 공간이 모자를 수 있기 때문에, 배열의 길이를 늘려주는 함수를 생성합니다.

def _increase_size(self):
    new_max_size = self.max_size * 2
    new_list = [None] * new_max_size
    for i in range(new_max_size):
        new_list[i] = self.list[i]
    self.max_size = new_max_size
    self.list = new_list

new_max_size = self.max_size * 2   원래길이의 2배 사이즈 지정
new_list = [None] * new_max_size    2배 길이의 리스트를 새로 만들어주고(None으로 공간을 채워줌)

for i in range(new_max_size):
    new_list[i] = self.list[i]                    원래 리스트의 데이터을 새로운 리스트에 넣어줌
self.max_size = new_max_size        리스트 길이가 2배가 됨
self.list = new_list                              새로운 리스트가 우리의 리스트가 됨

 

[ add ] 

arraylist에서 데이터 추가기능은 원래 배열의 끝에 추가됩니다.

def add(self, value):
    if self.size >= self.max_size:
        self._increase_size()   
    self.list[self.size] = value
    self.size += 1

  

    if self.size >= self.max_size:      데이터를 추가할 공간이 없으면 공간을 늘려준 다음
        self._increase_size()   
    self.list[self.size] = value            원래 배열의 끝에 데이터 추가
    self.size += 1                                추가됐으니까 사이즈 +1

 

[ insert ] 

arraylist에서 데이터 삽입기능도 인덱스를 지정해 바로 삽입가능합니다. 하지만, 중간에 데이터를 삽입했으니 추가한 데이터 이후로 한칸씩 뒤로 미뤄주는 작업이 추가적으로 필요합니다. 그래서, 시간복잡도 O(N)이 소요됩니다.

def insert(self, idx, value):
    if self.size >= self.max_size:
        self._increase_size()   
    for i in range(idx, self.size+1):
        self.list[i+1] == self.list[i] 
    self.list[idx] = value
    self.size += 1

    for i in range(idx, self.size+1):
        self.list[i+1] == self.list[i]           삽입할 공간을 만들어 주기 위해 하나씩 뒤로 미룸

    self.list[idx] = value           공간에 데이터를 삽입
    self.size += 1                       삽입했으니 사이즈 +1

 

[ delete ] & [ delete by index ]

delete기능은 입력한 데이터 값으로 삭제하고, delete by index는 입력한 인덱스의 데이터를 삭제합니다. 삭제 기능도 삽입기능과 마찬가지로 데이터 삭제 후 생긴 빈공간을 매꾸기위해 데이터를 하나씩 앞으로 땡겨옵니다.

def delete(self, value):
    for i in range(self.size):
        if self.list[i] == value:
            for j in range(i,self.size):
                self.list[j] == self.list[j+1]
            self.size -= 1
        else:
            raise Exception ("Can not find the data")

    for i in range(self.size):             배열에서
        if self.list[i] == value:             입력한 데이터값과 같은 데이터가 발견되면

            for j in range(i,self.size):     
                self.list[j] == self.list[j+1]        하나씩 땡겨와서 덮어버림
            self.size -= 1                                사이즈 -1
        else:                                       데이터를 못찾은 경우 예외 발생
            raise Exception ("Can not find the data")

def deletebyidx(self, idx):  
    if idx < 0 or idx > self.size:    #입력한 인덱스가 배열의 길이보다 큰 경우 예외 발생
        raise Exception ("Invalid Index")
    for i in range(idx, self.size):
        self.list[i] = self.list[i+1]
    self.size -= 1

 

# 전체 코드

전체코드와 다른 기능들은 깃허브를 참고하시면 됩니다.

https://github.com/sonzwon/TIL/blob/master/data_structure_List.py

GitHub - sonzwon/TIL: Today I Learned