[자료구조]Linked List로 여러 구조 구현

1. Stack with Linked List

1) 스택에 쓰이는 연산

• 파이썬의 기본적인 리스트 자료형은 append()와 pop()메서드를 제공
• append와 pop 모두 시간 복잡도는 O(1)
• 따라서 일반적으로 Stack을 구현할때는 List를 사용한다.

2) 리스트를 이용한 스택 구현

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        # 마지막 위치에 원소 삽입
        self.stack.append(data)

    def pop(self):
        if self.is_empty():
            return None
        # 마지막 원소 추출
        return self.stack.pop()

    def top(self):
        if self.is_empty():
            return None
        # 마지막 원소 반환
        return self.stack[-1]

    def is_empty(self):
        return len(self.stack) == 0

3) 연결 리스트로 스택 구현

• 연결 리스트로 스택을 구현하면 삽입(push)와 삭제(pop)연산에 있어서 O(1)의 시간 복잡도(Time Complexity)를 보장한다.
• 연결 리스트로 구현할 때는 머리(head)를 가리키는 하나의 포인터만 가진다.

• 머리(head): 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터

• 삽입할 때는 머리(head) 위치에 데이터를 넣는다
• 삭제할 때는 머리(head) 위치에서 데이터를 꺼낸다.

[Input]

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


class Stack:
    def __init__(self):
        self.head = None

    # 원소 삽입
    def push(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    # 원소 추출하기
    def pop(self):
        if self.is_empty():
            return None

        # 머리(head) 위치에서 노드 꺼내기
        data = self.head.data
        self.head = self.head.next

        return data

    # 최상위 원소(top)
    def top(self):
        if self.is_empty():
            return None
        return self.head.data

    # 먼저 추출할 원소부터 출력
    def show(self):
        cur = self.head
        while cur:
            print(cur.data, end=" ")
            cur = cur.next

    # 스택이 비어있는지 확인
    def is_empty(self):
        return self.head is None

## 클래스를 실행해보기, for문을 이용한 generator를 이용해 실행
stack = Stack()
arr = [9, 7, 2, 5, 6, 4, 2]
for x in arr:
    stack.push(x)
stack.show()
print()

while not stack.is_empty():
    print(stack.pop())

[Output]

2 4 6 5 2 7 9 
2
4
6
5
2
7
9

2. Queue with Linked List

1) 큐에 쓰이는 연산

• 큐는 먼저 삽입된 데이터가 먼저 추출되는 자료구조
  • Ex) 게임 대기 큐는 먼저 대기한 사람이 먼제 게임에 매칭된다.
  • Ex) 은행 대기열은 먼저 번호표를 뽑은 사람이 먼저 업무를 본다.
• enqueue(삽입), dequeue(삭제)
• front 연산은 dequeue를 했을 때, 실제 self.items의 value를 삭제하는 대신, self.front_index를 증가시킴으로써 dequeue한 값을 함수 상에서 얻는 값 취급을 했다.
  front연산은 삭제하지 않고 리턴만 하기때문에 self.items[self.fornt_index]를 리턴해주기만 하면 된다.

2) 리스트를 이용한 큐 구현

class Queue():
    def __init__(self):
        self.items = []
        self.front_index = 0

    def enqueue(self, value):
        self.items.append(value)

    def dequeue(self):
        if self.front_index == len(self.items):
            print('queue empty')
            return None
        else:
            returnvalue = self.items[self.front_index]
            self.front_index += 1
            return returnvalue
   
    def front(self):
        if self.front_index == len(self.items):
            print('queue is empty')
        else:
            returnvalue = self.items[self.front_index]
            return returnvalue

3) 연결 리스트를 이용한 큐 구현

• 연결 리스트로 큐을 구현하면 삽입(push)와 삭제(pop)연산에 있어서 O(1)의 시간 복잡도(Time Complexity)를 보장한다.
• 연결 리스트로 구현할 때는 머리(head)와 꼬리(tail) 두 개의 포인터를 가진다.
• 머리(head): 남아있는 원소 중 가장 먼저 들어온 데이터를 가리키는 포인터

• 꼬리(tail): 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터

• 삽입할 때는 꼬리(tail) 위치에 데이터를 넣는다.
• 삭제할 때는 머리(head) 위치에서 데이터를 꺼낸다.

[Input]

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


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, data):
        node = Node(data)
        if self.head == None:
            self.head = node
            self.tail = node
        # 꼬리(tail) 위치에 새로운 노드 삽입
        else:
            self.tail.next = node
            self.tail = self.tail.next

    def dequeue(self):
        if self.head == None:
            return None

        # 머리(head) 위치에서 노드 꺼내기
        data = self.head.data
        self.head = self.head.next

        return data

    def show(self):
        cur = self.head
        while cur:
            print(cur.data, end=" ")
            cur = cur.next


queue = Queue()
data_list = [3, 5, 9, 8, 5, 6, 1, 7]

for data in data_list:
    queue.enqueue(data)

print("\n전체 노드 출력:", end=" ")
queue.show()

print("\n[원소 삭제]")
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())

print("[원소 삽입]")
queue.enqueue(2)
queue.enqueue(5)
queue.enqueue(3)

print("전체 노드 출력:", end=" ")
queue.show()

[Output]

전체 노드 출력: 3 5 9 8 5 6 1 7 
[원소 삭제]
3
5
9
[원소 삽입]
전체 노드 출력: 8 5 6 1 7 2 5 3

3. Deque with Linked List

1) 덱의 연산

• 덱(Deque) = 스택(Stack) + 큐(Queue)
• 포인터 변수가 더 많이 필요하기 때문에, 메모리는 상대적으로 더 많이 필요하다.
• Python에서는 큐(queue)의 기능이 필요할 때 간단히 덱(deque)을 사용한다.
• 데이터의 삭제와 삽입 모두 시간 복잡도는 O(1)
  • Python에서는 덱(deque) 라이브러리를 사용할 수 있다.
  • 아래의 모든 매서드는 최악의 경우 시간 복잡도 O(1)을 보장한다.
  • 우측 삽입: append()
  • 좌측 삽입: appendleft()
  • 우측 추출: pop()
  • 좌측 추출: popleft()

2) 리스트를 이용한 덱 구현

class deque():
    def __init__(self):
        self.items = []
        self.front_value = 0



    def push(self, value):
        self.items.append(value)

    def pushleft(self, value):
        self.items.insert(self.front_value,value)

    def pop():
        if len(self.items) == self.front_value:
            print('queue is empty')
            return None
        else:
            return self.items.pop()

    def popleft():
        if len(self.items) == self.front_value:
            print('queue is empty')
            return None
        else:
            x = self.items[self.front_value]
            self.front_value += 1
            return x

• 파이썬 라이브러리를 사용했을 때

from collections import deque


d = deque()
arr = [5, 6, 7, 8]
for x in arr:
    d.append(x)
arr = [4, 3, 2, 1]
for x in arr:
    d.appendleft(x)
print(d)

while d:
    print(d.popleft())

arr = [1, 2, 3, 4, 5, 6, 7, 8]
for x in arr:
    d.appendleft(x)
print(d)

while True:
    print(d.pop())
    if not d:
        break
    print(d.popleft())
    if not d:
        break

3) 연결 리스트를 이용해 덱 구현

• 덱(deque)을 연결 리스트로 구현하면 삽입(push)와 삭제(pop)연산에 있어서 O(1)의 시간 복잡도(Time Complexity)를 보장한다.
• 연결 리스트로 구현할 때는 앞(front)과뒤(rear) 두 개의 포인터를 가진다.
• 앞(front): 가장 좌측에 있는 데이터를 가리키는 포인터
• 뒤(rear) : 가장 우측에 있는 데이터를 가리키는 포인터
  • 기본적인 파이썬 리스트 자료형은 큐(queue)의 기능을 제공하지 않는다.
  • 가능하다면 파이썬에서 제공하는 덱(deque) 라이브러리를 사용한다.
  • 큐의 기능이 필요할 때는 덱 라이브러리를 사용하는 것을 추천한다.
  • 삽입과 삭제에 대하여 모두 시간 복잡도는 O(1)이 요구된다.

[Input]

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


class Deque:
    def __init__(self):
        self.front = None
        self.rear = None
        self.size = 0

    def appendleft(self, data):
        node = Node(data)
        if self.front == None:
            self.front = node
            self.rear = node
        else:
            node.next = self.front
            self.front.prev = node
            self.front = node
        self.size += 1

    def append(self, data):
        node = Node(data)
        if self.rear == None:
            self.front = node
            self.rear = node
        else:
            node.prev = self.rear
            self.rear.next = node
            self.rear = node
        self.size += 1

    def popleft(self):
        if self.size == 0:
            return None
        # 앞에서 노드 꺼내기
        data = self.front.data
        self.front = self.front.next
        # 삭제로 인해 노드가 하나도 없는 경우
        if self.front == None:
            self.rear = None
        else:
            self.front.prev = None
        self.size -= 1
        return data

    def pop(self):
        if self.size == 0:
            return None
        # 뒤에서 노드 꺼내기
        data = self.rear.data
        self.rear = self.rear.prev
        # 삭제로 인해 노드가 하나도 없는 경우
        if self.rear == None:
            self.front = None
        else:
            self.rear.next = None
        self.size -= 1
        return data

    def front(self):
        if self.size == 0:
            return None
        return self.front.data

    def rear(self):
        if self.size == 0:
            return None
        return self.rear.data

    # 앞에서부터 원소 출력
    def show(self):
        cur = self.front
        while cur:
            print(cur.data, end=" ")
            cur = cur.next


d = Deque()
arr = [5, 6, 7, 8]
for x in arr:
    d.append(x)
arr = [4, 3, 2, 1]
for x in arr:
    d.appendleft(x)
d.show()

print()
while d.size != 0:
    print(d.popleft())

arr = [1, 2, 3, 4, 5, 6, 7, 8]
for x in arr:
    d.appendleft(x)
d.show()

print()
while True:
    print(d.pop())
    if d.size == 0:
        break
    print(d.popleft())
    if d.size == 0:
        break

[Output]

1 2 3 4 5 6 7 8 
1
2
3
4
5
6
7
8
8 7 6 5 4 3 2 1 
1
8
2
7
3
6
4
5

DataStructure 카테고리 내 다른 글 보러가기