먹고 기도하고 코딩하라

파이썬과 자료구조 - (1) 배열, 연결 리스트 본문

자료구조&알고리즘/이론

파이썬과 자료구조 - (1) 배열, 연결 리스트

2G Dev 2021. 8. 18. 09:32
728x90
728x90

 

파이썬은 비교적 자유도가 높은 언어이다. (확실히 C나 Java에 비해서는) 동적 타이핑이 가능하고, 언제든 변수의 타입을 바꿀 수도 있다. 그래서인지 리스트 하나의 내장 메소드를 사용해 배열, 큐, 스택을 쉽게 만들 수 있는 등 장점이 많다.

이번 포스팅에서는 배열과 연결 리스트, 스택과 큐, 덱까지 살펴보겠다.

 

먼저 ADT의 개념부터...

ADT(Abstract Data Type)란 유사 동작을 하는 자료구조 클래스에 대한 모델을 가리킨다. 어떤 프로그래밍 언어로 구현된 것이 아니고 단지 이 자료구조가 어떤 동작을 하며 어떤 프로퍼티를 갖는지... 뭐 그런 것들을 기술한 것이다. 추상 데이터 타입이라고도 부른다.

 

 

 

1. 배열

배열(Array)은 가장 익숙한 자료구조일 것이다. 요소들이 연속된 메모리에 순차적으로 저장되는 자료구조이다. 파이썬의 기본 리스트가 배열과 가장 비슷한 자료구조이다. 

# 배열 초기화
lst = []

# 맨 끝에 삽입
lst.append(1)
# 특정 위치에 삽입
lst.insert(0, 5)	# 0번 위치에 5 추가
# 특정 위치에 삽입
lst.insert[2] = 3

# 맨 끝 요소 삭제
lst.pop()
# 특정 위치 요소 삭제
lst.pop(1)	# 1번 위치 요소 삭제
# 특정 요소 삭제
lst.remove(5)	# 리스트에서 5 삭제

# 검색
lst.index(1)	# 리스트에서 1의 위치 반환

# 접근
lst[1]	# 1번 위치에 접근

# 순회
for e in lst:
    print(e)
  • 삽입 - append(x) : 리스트의 맨 뒤에 x를 삽입한다. 시간복잡도 O(1)
  • 삽입 - insert(i, x) : 리스트의 i번째 위치에 x를 삽입한다. 시간복잡도 O(n)
  • 삭제 - pop() : 리스트의 맨 뒤 요소 1개를 삭제한다. 시간복잡도 O(1)
  • 삭제 - pop(i) : 리스트의 i번째 요소 1개를 삭제한다. 시간복잡도 O(n)
  • 삭제 - remove(x) : 리스트 요소들 중 x와 일치하는 것을 삭제한다. 시간복잡도 O(n)
  • 삭제 - del(lst) : lst 리스트를 삭제한다. 시간복잡도 O(n)
  • 검색 - index(x) : 리스트를 맨 앞부터 검색해서 x를 찾아 그 인덱스를 반환한다. 없을 경우 ValueError가 발생한다. 시간복잡도 O(n)
  • 접근 - [i] : i번 인덱스의 요소에 접근할 수 있다. 만약 리스트의 길이보다 크거나 같은 숫자를 입력했을 경우 IndexError가 발생한다. 시간복잡도 O(n)

사실 파이썬에서는 배열과 연결 리스트를 구분짓는 게 무의미한 일이 아닌가 싶기도 하다. 기본 리스트를 써도 연결 리스트처럼 구현하기 쉽기 때문이다. 하지만 정석대로 연결 리스트도 만들어보자.

 

 

 

2. 연결 리스트

연결 리스트(Linked list)는 값, 리스트의 다음 노드에 대한 레퍼런스를 갖는 노드들로 이뤄진 선형 리스트이다. 마지막 노드는 레퍼런스로 null 값(None)을 가진다. 연결 리스트로 스택과 큐를 구현할 수도 있다.

일단 클래스로 노드를 한 번 만들어 보자. 노드 1개는 valuenext pointer를 가진다.

# node.py
class Node:
  def __init__(self, value=None, pointer=None):
    self.value = value
    self.pointer = pointer

  def getData(self):
    return self.value

  def getNext(self):
    return self.pointer
  
  def setData(self, value):
    self.value = value
  
  def setNext(self, pointer):
    self.pointer = pointer

직관적인 Node 클래스이다. 데이터를 가져오고 지정하고, next 포인터를 가져오고 지정하는 등의 역할만 수행한다.

이제 이를 이용해 연결 리스트를 만들어 보자. 미아 스타인의 <파이썬 자료구조와 알고리즘>에 나오는 FIFO 연결리스트를 구현해 보자. 이 클래스는 특이하게도 값과 인덱스로 값을 삭제하는 메소드가 있다. (C로 공부할 때, 연결 리스트의 delete 메소드는 당연히 head부터 삭제를 했는데, 저자가 누구인지에 따라 삭제나 탐색을 어떻게 구현할지 달라지는 모양이다)

이 연결리스트는 길이를 나타내는 length와 head, tail 포인터와 여러 노드들로 이루어져 있다.

 

from node import Node

class LinkedListFIFO:
  def __init__(self):
    self.length = 0	# 리스트가 비어 있을 때의 삽입, 삭제 및 탐색을 위해 length를 둠
    self.head = None	# head와 tail 포인터를 정한다
    self.tail = None

  def printList(self):	# head부터 tail까지 값을 출력하는 메소드
    node = self.head
    while node:
      print(node.getData(), end=' ')
      node = node.getNext()
    print()
  
  def _addFirst(self, value):	# 맨 앞에 데이터를 삽입하는 메소드, 즉 리스트가 비었을 때 삽입
    node = Node(value)
    self.length = 1
    self.head = node
    self.tail = node

  # 이게 실행된다는 건 리스트의 최후까지 다 지우는 판국이라는 뜻이다
  def _deleteFirst(self):
    self.length = 0
    self.head = None
    self.tail = None
    print('연결 리스트가 비었습니다.')

  # 일반적인 경우의 새 노드 추가
  def _add(self, value):
    self.length += 1
    node = Node(value)
    if self.tail:	# 만약 tail이 None이 아닌 경우, 즉 비어있지 않다면 맨 마지막 요소의 next를 Node로 한다
      self.tail.setNext(node)
    self.tail = node	# 어떤 경우이든 맨 뒤에 삽입한 것이므로 tail이 node를 가리키도록 한다

  # 새 노드 추가
  def addNode(self, value):
    if not self.head: # head가 None이라면.. 즉, 리스트가 비었다면
      self._addFirst(value)
    else: 
      self._add(value)
    
  def find(self, idx):
    prev = None
    node = self.head
    i = 0
    while node and i < idx:
      prev = node
      node = node.getNext()
      i += 1
    return node, prev, i

  def findByValue(self, value):
    prev = None
    node = self.head
    found = False
    while node and not found:
      if node.getData() == value:
        found = True
      else:
        prev = node
        node = node.getNext()
    return node, prev, found

  def deleteNode(self, idx):
    # 리스트가 비거나 1개밖에 없을 경우
    if not self.head or not self.head.getNext():
      self._deleteFirst()
    else:
      node, prev, i = self.find(idx)
      if i == idx and node: # 그 자리에 노드가 있을 경우
        self.length -= 1
        if i == 0 or not prev:  # head일 경우
          self.head = node.getNext()
          self.tail = node.getNext()
        else:
          prev.setNext(node.getNext())
      else:
        print(f'{idx} 자리에 노드가 없습니다.')
  
  def deleteNodeByValue(self, value):
    if not self.head or not self.head.getNext():
      self._deleteFirst()
    else:
      node, prev, i = self.findByValue(value)
      if node and node.getData() == value:
        self.length -= 1
        if i == 0 or not prev:
          self.head = node.getNext()
          self.tail = node.getNext()
        else:
          prev.setNext(node.getNext())
      else:
        print('값 {}에 해당하는 노드가 없습니다.'.format(value))

LinkedListFIFO 클래스에서 우리는 초기화, 순차 순회, 삽입, 삭제, 탐색을 할 수 있다. 이 때 삭제를 위해 탐색을 진행하게 되므로 LinkedListFIFO 클래스의 핵심 기능은 삽입, 삭제, 순회라고 할 수 있다.

사실 연결 리스트의 경우 파이썬에서는 그냥 일반 리스트로 구현이 가능한 기능이지만 C스럽게 구현한 모습이다. (출처는 미아 스타인의 '파이썬 자료구조와 알고리즘'. 좋은 책이다) 

연결 리스트의 경우 삽입 시간복잡도 O(1), 선택 삭제 시간복잡도 O(n), 순회 시간복잡도 O(n), 탐색 시간복잡도 O(n)이 소요된다.

 

다음에는 스택과 큐, 덱에 대해 알아보겠다.

 

 

 

References

  • 미아 스타인, <파이썬 자료구조와 알고리즘>

 

728x90
반응형
0 Comments
댓글쓰기 폼