문서 목적

문서 목적 해당 문서는 대학원 과정 중 파이썬과 자료구조에 대해 정리하고자 작성된 문서이다.

리스트

선형 자료구조로, Python에서는 이를 기본적으로 제공한다.

ADT of list

i번 자리에 원소 x를 삽입한다.
i번 원소를 삭제한다.
원소 x를 삭제한다.
i번 원소를 알려준다.
원소 x가 몇 번 원소인지 알려준다.
리스트의 사이즈(원소의 총 수)를 알려준다.

배열 리스트

method

• insert(x, i) : x를 리스트의 i번 원소로 삽입
  • 0번 인덱스에 데이터를 삽입하는 경우 효율이 가장 나쁘다.
  • 원소를 삽입 시 해당 인덱스 이후에 있는 원소들은 모두 시프트 하게 된다.
  • 마지막 인덱스에 삽입 하는 경우, 가장 효율이 좋음
• append(x) : 원소 x를 리스트의 맨 뒤에 추가
  • data.insert(len(data), x) 와 같음
• pop(i) : i번째 원소를 삭제하면서 알려준다.
  • 데이터를 꺼내면 해당 인덱스 이후의 원소들은 0쪽으로 시프트가 이루어진다.
  • 맨 마지막은 -1을 이용해서 빼는 방법이 있음
• remove(x) : 리스트에서 처음으로 나타나는 x를 삭제한다.
• index(x) : x가 리스트의 몇 번 원소인지 알려준다.
• clear() : 리스트를 깨끗이 청소한다.
• count(x) : x가 몇번 나타나는지 알려준다.
• extend(a) : 리스트에 나열할 수 있는 객체 a를 풀어서 추가
• copy() : 리스트를 복사
• reverse() : 리스트의 순서를 역으로 뒤집는다.
• sort() : 리스트 정렬

Python 내장 리스트의 한계

• lowlevel(하부)가 배열로 구현되어 있음
• 배열의 단점인 아래를 가질 수 밖에 없음
  • 연속된 공간에 저장되므로 삽입이나 삭제 시 시프트 작업이 필요
  • 미리 크기를 정해야 하므로 오버플로우 시 배열을 새로 배정받아 내용을 복사함
• 사용자 입장에서는 신경 쓸 필요가 없다고 하나, production 환경에서는 신경 쓸 필요가 종종 있음
  • 종종 시물레이션을 돌릴 시, 코드를 아래와 같이 짜는 습관이 있음

count = 1000
result = [0 for _ in range]
for i in range(count):
	result[i] += 1

linked list

method

• __head : 첫 번째 노드에 대한 레퍼런스
• __numItems : 연결 리스트에 들어 있는 원소의 총 수
• insert(i, x) : x를 연결 리스트의 i번 원소로 삽입한다.
• append(x) : 연결 리스트의 맨 뒤에 원소 x를 추가한다.
• pop(i) : 연결 리스트의 i번 원소를 삭제하면서 알려준다.
• remove(x) : 연결 리스트에서 처음으로 나타나는 x를 삭제한다.
• get(i) : 연결 리스트의 i번 원소를 알려준다.
• index(x) : 원소 x가 연결리스트의 몇 번 원소인지 알려준다.
• isEmpty() : 연결 리스트가 비어 있는지 알려준다.
• size() : 연결 리스트의 총 원소 수를 알려준다.
• clear() : 연결 리스트를 깨끗이 청소한다.
• count(x) : 연결 리스트에서 원소 x가 몇 번 나타나는지 알려준다.
• extend(a) : 연결 리스트에서 나열할 수 있는 객체 a를 풀어서 추가한다.
• copy() : 연결 리스트를 복사해서 새 연결 리스트를 리턴한다.
• reverse() : 연결 리스트의 순서를 역으로 뒤집는다.
• sort() : 연결 리스트를 정렬한다.

객체 구조

• node는 item과 next를 가지고 있다.
  • item은 데이터 값이 들어감
  • next는 다음 node를 가리키는 포인터

head node

• 연결 리스트는 흔히 첫 노드에 대한 레퍼런스를 갖고 있으며, 이를 head node라고 한다.

Code

sort는 나중에...ㅎㅎ

class Node:
    def __init__(self, data, nextNode=None):
        self.data = data
        self.nextNode = nextNode


class LinkedList:
    # TODO: sort, reverse 추가
    def __init__(self, node=None):
        self.__head = node
        self.__numItems = 0 if node is None else 1
        
    def __check_valid_node(self, node):
        if node.__class__.__name__ != 'Node':
            raise ValueError(f'x must be Node class, but got {node.__class__.__name__}')
    
    def __get_node_item(self, i):
        if self.__numItems <= i:
            raise IndexError(f'max_size is {self.__numItems} but got {i}')
        curNode = self.__head
        for _ in range(i):
            curNode = curNode.nextNode
        return curNode
    
    def __get_last_node_item(self):
        curNode = self.__head
        while curNode.nextNode is not None:
            curNode = curNode.nextNode
        
        return curNode
        
    def insert(self, i, x):
        # `insert(i, x)` : x를 연결 리스트의 i번 원소로 삽입한다.
        
        self.__check_valid_node(x)
        
        curNode = self.__get_node_item(i)
        nextNode = curNode.nextNode
        curNode.nextNode = x
        x.nextNode = nextNode
        self.__numItems += 1
        self.describe()
    
    def append(self, x):
        #`append(x)` : 연결 리스트의 맨 뒤에 원소 x를 추가한다.
        self.__check_valid_node(x)
        if self.__numItems == 0:
            self.__head = x
        else:
            curNode = self.__get_last_node_item()
            curNode.nextNode = x
        self.__numItems += 1
        self.describe()
    
    def pop(self, i):
        # `pop(i)` : 연결 리스트의 i번 원소를 삭제하면서 알려준다.
        curNode = self.__get_node_item(i-1)
        removedNode = curNode.nextNode     
        removedNextNode = removedNode.nextNode if removedNode is not None else None

        curNode.nextNode = removedNextNode
        self.__numItems -= 1
        self.describe()
        return removedNode
    
    def remove(self, x):
        # `remove(x)` : 연결 리스트에서 처음으로 나타나는 x를 삭제한다.
        pervNode = None
        isChanged = False
        curNode = self.__head
        while curNode is not None:
            if curNode.data == x.data:
                if pervNode is None:
                    self.__head = curNode.nextNode
                else:
                    pervNode.next = curNode.nextNode
                isChanged = True
                break
            curNode = curNode.nextNode
            pervNode = curNode
        
        if isChanged:
            self.__numItems -= 1
        else:
            raise ValueError(f'{x} is not in Linkedlist')
        self.describe()
    
    def get(self, i):
        # `get(i)` : 연결 리스트의 i번 원소를 알려준다.
        return self.__get_node_item(i)
    
    def index(self, x):
        # `index(x)` : 원소 x가 연결리스트의 몇 번 원소인지 알려준다.
        idx = 0
        curNode = self.__head
        isFind = False
        while curNode is not None:
            if curNode.data == x.data:
                isFind=True
                return idx
            idx += 1
            curNode = curNode.nextNode
        if not isFind:
            raise ValueError(f'{x} is not in Linkedlist')
            
    def isEmpty(self):
        # `isEmpty()` : 연결 리스트가 몇 번 원소인지 알려준다.
        return True if self.__numItems == 0 else False
    
    def size(self):
        # `size()` : 연결 리스트의 총 원소 수를 알려준다.
        return self.__numItems
    
    def clear(self):
        # `clear()` : 연결 리스트를 깨끗이 청소한다.
        self.__head = None
        self.__numItems = 0
        
    def count(self, x):
        # `count(x)` : 연결 리스트에서 원소 x가 몇 번 나타나는지 알려준다.
        count = 0
        curNode = self.__head
        while curNode is not None:
            if curNode.data == x.data:
                count += 1
            curNode = curNode.nextNode
            
        return count
    
    def extend(a):
        # `extend(a)` : 연결 리스트에서 나열할 수 있는 객체 a를 풀어서 추가한다.
        lastNode = self.__get_last_node_item()
        if a.__class__.__name__ == 'LinkedList':
            lastNode.next(a.__head)
        else:
            for node_i in a:
                self.append(node_i)
        self.describe()
    def copy():
        # `copy()` : 연결 리스트를 복사해서 새 연결 리스트를 리턴한다.
        newLinkedList = LinkedList()
        curNode = self.__head
        while curNode.nextNode is not None:
            newLinkedList.append(curNode)
            curNode = curNode.nextNode
        
        return newLinkedList
    
    def describe(self):
        curNode = self.__head
        list_i = []
        for _ in range(self.__numItems):
            list_i.append(curNode.data)
            curNode = curNode.nextNode if curNode is not None else None
        print(list_i)
   

특징

• 연속되지 않은 공간에 저장되어 링크를 관리하는 부담 존재
• 인덱스가 주어진 접근도 링크를 따라가는 부담이 있음
• 삽입이나 삭제 시 시프트 작업이 필요 없음.
• 원소가 추가될 때 동적으로 공간을 할당 받으므로 원소의 수에 비례하는 공간만이 소요
• 오버플로우에 자유로움

배열 리스트 vs 연결리스트

• insert
  • 배열 리스트 : 위치 접근 $\Theta(1)$, 삽입 작업 $\Omicron(n)$
  • 연결 리스트 : 위치 접근 $\Omicron(n)$, 삽입 작업 $\Theta(1)$
• pop
  • 배열 리스트 : 위치 접근 $\Theta(1)$, 삽입 작업 $\Omicron(n)$
  • 연결 리스트 : 위치 접근 $\Omicron(n)$, 삽입 작업 $\Theta(1)$
• remove
  • 배열 리스트 : 위치 접근 $\Omicron(n)$, 삽입 작업 $\Omicron(n)$
  • 연결 리스트 : 위치 접근 $\Omicron(n)$, 삽입 작업 $\Theta(1)$
• get
  • 배열 리스트 : $\Theta(1)$
  • 연결 리스트 : $\Omicron(n)$

원형 연결 리스트 (Circular LinkedList)

끝 노드(tail)의 nextNode가 None을 갖는 대신 첫 노드를 링크한다
맨 앞과 맨 뒤의 접근성 차이가 없어짐

양방향 연결 리스트(Doubly Linked list)

각 노드가 nextNode만 가지고 있는 것이 아닌 prevNode 또한 링크함
head의 경우 prevNode는 Node을 갖고 있음

양방향 원형 연결 리스트(Circular Doubly Linked List)

원형 연결 리스트 + 양방향 연결 리스트