연결 리스트(Linked List) 응용

2019-04-11

Linked List

Linked List를 이용한 Stack 구현

class Node:
    def __init__(self, data=None):
        self.__data = data
        self.__next = None
        
    @property
    def data(self):
        return self.__data
    
    @data.setter
    def data(self, data):
        self.__data = data
        
    @property
    def next(self):
        return self.__next
    
    @next.setter
    def next(self, n):
        self.__next = n


class LStack:
    def __init__(self):
        self.top = None
        
    def empty(self):
        if self.top is None:
            return True
        else:
            return False
        
    def push(self, data):
        new_node = Node(data)
        
        new_node.next = self.top
        self.top = new_node
    
    def pop(self):
        if self.empty():
            return
        
        cur = self.top
        self.top = self.top.next
        
        return cur.data
    
    def peek(self):
        if self.empty():
            return
        
        return self.top.data


if __name__ == '__main__':

    s = LStack()
    
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    s.push(5)
    
    while not s.empty():
        print(s.pop(), end = " ")

>> 5 4 3 2 1

Linked List를 이용한 Queue 구현

class Node:
    def __init__(self, data=None):
        self.__data = data
        self.__next = None
        
    @property
    def data(self):
        return self.__data
    
    @data.setter
    def data(self, data):
        self.__data = data
        
    @property
    def next(self):
        return self.__next
    
    @next.setter
    def next(self, n):
        self.__next = n


class LQueue:

    def __init__(self):
        self.front = None
        self.rear = None
        
    def empty(self):
        if self.front is None:
            return True
        else:
            return False
        
    def enqueue(self, data):
        new_node = Node(data)
        
        # 데이터가 하나도 없는 경우, front와 rear은 모두 None을 가리키게 된다.
        # 이 상태에서는 front와 rear에 데이터가 없기 때문에 다음 데이터를
        # 가리킬 수 없다.
        # 따라서 front와 rear가 처음 데이터가 들어왔을 때, 그 데이터를 가리키게
        # 조건을 추가해야 한다.
        
        if self.front is None and self.rear is None:
            self.front = new_node
            self.rear = new_node
            return
        
        self.rear.next = new_node
        self.rear = new_node
    
    def dequeue(self):
        if self.empty():
            return
        
        # 만약 데이터가 한 개 남았을 경우, front와 rear가 같은 데이터를 가리킴
        # front에 있는 데이터를 지역변수로 가리키게 하고 front를 front 다음 데이터로
        # 옮겨도 rear이 계속 지역변수가 가리키고 있는 데이터를 같이 가리키게 된다.
        # 이렇게 된다면 레퍼런스 카운트가 0이 되지 않아 데이터가 지워지지 않는다.
        # 따라서 데이터가 하나 남은 상황이라면 즉, front와 rear이 같은 데이터를
        # 가리키고 있다면 rear도 rear의 다음 데이터를 가리키게 조건을 추가해야 한다.
        
        if self.front is self.rear:
            self.rear = self.rear.next
        
        cur = self.front
        
        self.front = self.front.next
        
        return cur.data
        
    def peek(self):
        if self.empty():
            return
        
        return self.front.data

        
if __name__ == '__main__':

    q = LQueue()
    
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    q.enqueue(5)
    
    while not q.empty():
        print(q.dequeue(), end = " ")

>> 1 2 3 4 5

배열(array) vs 연결 리스트(Linked List)

배열(array)
- 같은 자료형의 변수를 모아 놓은 것
- indexing(search)
- 데이터가 한군데 모여있다.(군집화)
- locality로 인해 cache hit가 많음
- 기본적으로 stack에 할당
- 검색속도가 빠름(O(1) - 빅오의 1순위)
- 데이터의 삽입과 삭제가 느림(O(n) - 빅오의 3순위)
- 데이터의 삽입과 삭제의 양이 많을 경우, 복사가 많이 일어나게 된다.
연결 리스트(Linked List)
- 데이터가 흩어져 있다.
- cache miss가 높다.
- heap에 할당
- 검색이 느림(O(n) - 빅오의 3순위)
- 데이터의 삽입과 삭제가 빠름(O(1) - 빅오의 1순위)
- dynamic heap을 통해 Linked List의 단점을 막을 수 있다.
두 가지 다 적용이 가능하다면 배열을 사용하는 것이 좋다.
python의 리스트는 배열이 아니다.
- 리스트는 포인터 배열
- 서로 다른 자료형이 들어갈 수 있음
- 상수가 리스트 안에 있을 때, 그 상수가 정수형이어도 4bytes가 아니다.
- 상수 객체이기 때문에 int() 클래스 안의 내장함수를 모두 포함하고 있어서
  용량이 크다.

Algorithm - Maze

미로찾기

stack 사용

class Node:

    def __init__(self, data):
        self.data = data
        self.next = None
        

class LinkedList:
    
    def __init__(self):
        self.head = None
        
    def empty(self):
        if not self.head:
            return True
        return False
    
    def add(self, data):
        new_node = Node(data)
        
        if not self.head:
            self.head = new_node
            return
        
        new_node.next = self.head
        self.head = new_node
        
    def traverse(self):
        cur = self.head
        while cur:
            yield cur
            cur = cur.next
            

class Position:
    
    def __init__(self, row, col, dir):
        self.row = row
        self.col = col
        self.dir = dir
        

class MazeSolver:
    
    direction = ((-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1))
    
    def __init__(self, maze):
        
        self.maze = maze
        
        # 출구 행, 열을 나타냄
        self.EXIT_ROW = len(maze)
        self.EXIT_COL = len(maze[0])
        
        # 맨 위 아래 옆에 1로된 벽 넣기
        # 1. maze의 row열 양 옆에 1 넣기
        for row in maze:
            row.insert(0, 1)
            row.append(1)
            
        # 2. maze의 위 아래로 1로 된 row 열 넣기
        added_row = [1 for _ in range(self.EXIT_COL+2)]
        maze.insert(0, added_row)
        maze.append(added_row)
        
        self.path = LinkedList()
        
    def get_path(self):
        stack = LStack()
        mark = []
        
        # mark를 0으로 가득 찬 실제 미로 크기의 리스트
        for _ in range(self.EXIT_ROW+2):
            mark.append([0 for _ in range(self.EXIT_COL+2)])
            
        row = None
        col = None
        dir = None
        
        next_row = None
        next_col = None
        found = None
        
        # 미로의 시작점(1, 1)
        mark[1][1] = 1
        # 첫 시작의 위치를 stack에 push
        stack.push(Position(1, 1, 2))
        
        # stack이 비었다면 목적지로 가는 길이 없다는 뜻이다.
        # 목적지에 도달했다면 while 문에서 빠져나와야 한다.
        while not stack.empty() and not found:
            
            # stack에서 pop을 한다.
            # 현재의 위치를 업데이트한다.
            
            pos = stack.pop()
            row = pos.row
            col = pos.col
            dir = pos.dir
            
            # dir을 조사한다.
            # 모든 방향을 조사했거나 목적지에 도착했다면 while 문에서 빠져나온다.
            while dir < 8 and not found:
                
                next_row = row + self.direction[dir][0]
                next_col = col + self.direction[dir][1]
                
                if next_row == self.EXIT_ROW and next_col == self.EXIT_COL:
                    found = True
                    stack.push(Position(row, col, dir))
                    stack.push(Position(next_row, next_col, 0))
                    
                elif mark[next_row][next_col] == 0 and maze[next_row][next_col] == 0:
                    mark[next_row][next_col] = 1
                    stack.push(Position(row, col, dir))
                    row = next_row
                    col = next_col
                    dir = 0
                    
                else:
                    dir += 1
                    
        if found:
            while not stack.empty():
                self.path.add(stack.pop())
        else:
            print('There is no path in this maze!')
            
    def print_path(self):
        g = self.path.traverse()
        for node in g:
            print("({}, {})".format(node.data.row, node.data.col))

    def show_maze(self):
        print('   ', end='')
        for i in range(self.EXIT_ROW+2):
            print(' ' + str(i) + ' ', end='')
        print()

        for i in range(self.EXIT_ROW+2):
            print(' ' + str(i) + ' ', end='')

            for j in range(self.EXIT_COL+2):
                if self.maze[i][j] == 0:
                    print(' O ', end='')
                else:
                    print(' # ', end='')
            print()
        print()

    def show_path(self):
        path_set = set()
        g=self.path.traverse()
        for node in g:
            path_set.add((node.data.row, node.data.col))

        print('   ', end='')
        for i in range(self.EXIT_ROW+2):
            print(' ' + str(i) + ' ', end='')
        print()



        for i in range(self.EXIT_ROW+2):
            print(' ' + str(i) + ' ', end='')

            for j in range(self.EXIT_COL+2):
                if (i, j) in path_set:
                    print(' P ', end='')
                elif self.maze[i][j] == 0:
                    print(' O ', end='')
                else:
                    print(' # ', end='')
            print()
        print()


if __name__ == "__main__":

    maze = [
        [0, 1, 1, 0, 0],
        [1, 0, 0, 1, 1],
        [0, 1, 1, 0, 1],
        [0, 1, 0, 1, 1],
        [1, 1, 0, 0, 0],
    ]

    maze_solver = MazeSolver(maze)

    maze_solver.show_maze()

    maze_solver.get_path()

    maze_solver.print_path()

    maze_solver.show_path()


>>    0  1  2  3  4  5  6 
   0  #  #  #  #  #  #  # 
   1  #  O  #  #  O  O  # 
   2  #  #  O  O  #  #  # 
   3  #  O  #  #  O  #  # 
   4  #  O  #  O  #  #  # 
   5  #  #  #  O  O  O  # 
   6  #  #  #  #  #  #  # 

   (1, 1)
   (2, 2)
   (2, 3)
   (3, 4)
   (4, 3)
   (5, 4)
   (5, 5)
       0  1  2  3  4  5  6 
    0  #  #  #  #  #  #  # 
    1  #  P  #  #  O  O  # 
    2  #  #  P  P  #  #  # 
    3  #  O  #  #  P  #  # 
    4  #  O  #  P  #  #  # 
    5  #  #  #  O  P  P  # 
    6  #  #  #  #  #  #  #

지눅쿠의 개발 블로그

StudyPython and CE

연결 리스트(Linked List) 응용

Linked List

배열(array) vs 연결 리스트(Linked List)

Algorithm - Maze