파이썬 | 링크드 리스트 | 자료구조 | 알고리즘
파이썬으로 링크드 리스트를 구현해본다.
파이썬의 링크드 리스트는 C언어의 링크드 리스트와는 몇가지 측면에서 다른데 어느 쪽이 더 쉽냐고 단정지어 말하기는 어렵다.
[C언어]
- C언어 같은 경우 매우 정확하게 동작 원리를 알게된다. 정확하게 알지 못하면 점하나 잘못 찍어도 작동하지 않는다.
- C언어는 처음에 이해하는데 시간이 오래 걸리지만 한번 이해하면 다른 것들도 쉽게 알게되는 경향이 있다. 아무래도 촘촘한 메모리 단위로 퍼즐을 풀듯이 데이터를 취급하기 때문이다.
- 성능 측정도 쉬운데 MS 비주얼 C++ 같은 디버거를 사용하면 CPU의 Instruction time 등 객관적인 수치도 측정하여 벤치마킹에 사용할 수 있다.
- 성능은 당연히 C언어가 좋다. 파이썬과 비교해서 최적화한 C언어가 100배 정도 뛰어나다고 하는데 과장은 아닐 것이다. (아래 성능 테스트를 참고) 그렇다고 파이썬으로 링크드 리스트를 만드는 의미가 없는 것은 아니다. 알고리즘이나 언어의 경쟁력을 단순한 성능 측정만 가지고 한다면 현재 파이썬의 인기는 설명이 불가능하다.
C++과 파이썬 루프 | i7-10700 컴퓨터성능 테스트 2 (i7-4790 과 비교)
i7-4790을 2014년도 부터 사용하다가 6년만에 i7-10700으로 바꿨다. 램도 DDR4를 달았다. 지난번 i7-4790 과 비교에서 for문의 성능이 얼마나 좋아졌나 알아보기로 한다. 지난번 테스트는 아래와 같다. C++
digiconfactory.tistory.com
[파이썬]
- 파이썬은 원래 추상화가 심한데다가 컨테이너로 클래스를 사용하니까 말로 이해하기는 쉬운 측면이 있다. 그런데 왜 그런지 구체적으로는 설명이 쉽지 않다. 아마 동적 타이프로 변수의 타입을 명시하지 않다보니 생기는 일이다. 파이썬에서는 클래스도 listA, 변수도 listA, 시퀀스도 listA 라고 선언해서 사용할 수 있다. 타입을 추론하는 직관력은 높아지지만 구체적인 연결 부분까지 고려가 잘 되지 않는다.
그런 부분은 자바 스크립트와도 유사하다. 객체지향 프로그래밍을 잘 알지 못하는 상태에서는 전달력이 떨어지기 쉽다. 반면 객체지향 프로그래밍의 경험이 많다면 훨씬 유연하게 사용할 수 있다. 설계할 때 정수를 저장하는 형태로 리스트를 만들었는데 이미 파이썬의 시퀀스(리스트, 튜플, 문자열 등)도 저장할 수 있는 리스트가 된다. C언어가 파이썬보다 물리적인 속도는 100배 빠를지 모르지만 사람이 하는 일은 이쪽이 더 빠를수 있다. (사람의 능력에 따라서 다르다)
파이썬은 인간 중심이고 C는 기계 중심이다. 이 세상에 문과와 이과가 있듯이 컴퓨팅의 세계도 스스로 진화하고 있다.
- 객체지향이면서 자바보다 코드 수가 적다. 초보자나 다른 전공의 사람들이 이해하기 편하다는 점이다. 이것은 컴퓨터공학자에게도 장점으로 사람들에게 코드내용을 이해시키는데 수고를 덜어준다. 자바는 OOP기준이 엄격하고 안정성있고 다 좋은데 코드가 길다. 코드가 길면 변수이름도 신경써서 지어야 되고 아무래도 동일한 코드를 작성해도 작업량이 늘어나는 것은 사실이다. 아마 자바 보다 나은 점일 것이다.
사실 컴퓨터 공학자 이외에 파이썬을 가장 빨리 도입한 사람들은 이과 쪽 사람들이다. 물리학, 수학, 통계학 등 파이썬을 사용해 논문을 쓰고 데이터의 검증을 하다가 인공지능까지 개발하는 단계에 와있다. 이들 과학도가 사용하는 상당수가 오픈소스라는 것은 놀라운 사실이다. 과학이 세상 밖으로 나오자 기술혁신이 가속화되는 것이다. MS의 OS 독점시장에서는 상당히 비쌌던 소프트웨어의 상당수가 지금은 무료거나 가격이 많이 싸졌다. 오픈 소스 그 자체인파이썬의 마인드도 인류의 미래지향적으로 볼 수 있다. 컴퓨터 이외의 과학도들이 개발하는 알고리즘이 상당히 중요해졌다.
- 파이썬의 장점과 단점에 대하여 이야기를 더 할 수 있지만 나중에 기회가 있을 때 하고 이 포스팅에서는 이정도로 해둔다.
* 노드 만들기
우선 노드를 만든다.
가장 쉽게 데이터와 포인터를 만든다. 초기값을 주면 None (C에서는NULL) 이다. 노드는 이게 끝이고 나머지는 LinkedList 클래스에서 구현한다.
* 링크드 리스트
생성자를 만든다. 보는 것 처럼 비어있다. 링크드리스트 클래스는 head (포인터다)를 갖는다. 노드의 첫번째 포인터로 보면된다. length는 인덱스를 사용하기 위해 넣었다. 인덱스를 넣지 않아도 키값으로 검색할 수 있지만 좀더 편리하게 사용할 수 있다.
- C언어로 알고리즘을 만들 때는 모두가 성능에 집착하는 부분이 있는데 파이썬의 알고리즘은 조금 다른 관점에서 볼 필요가 있다. 성능의 최적화도 중요하지만 지금 상황에서 사람이 더 쉽게 일하는 부분도 똑같이 중요하다.
파이썬을 수십년 다뤄온 한 엔지니어는 자신의 저서 '파이썬 알고리즘' 에서 성능이 정말로 중요하다면 C언어나 C++을 사용해서 개발하라고 조언한다. 100배나 느릴지 모르는 파이썬에서 한 두줄의 코드로 결정적인 차이를 만들어 내는 것은 어렵다. 전문가가 파이썬으로 가장 아름답고 빠른 코드를 만들어도 초보자가 C언어로 대충 짠 코드보다 수십배 성능이 떨어질 수 있다.
그보다 파이썬 알고리즘을 설계할 때는 사람들이 일할 때 생산성을 높일 수 있도록 하라고 한다. 흠... 무슨 말인지 쉽지는 않다. 그 중에 하나는 소스 코드를 읽기 쉽게 만든다던가 PEP8을 잘 지키던가... 아니면 C언어로 클래스를 하나 만들동안 5개의 클래스를 만들라고 하거나; 뭐 그런 것이라고 추측해본다. 이런 논의는 앞으로도 발전적으로 해야할 것이다.
성능보다 편의를 위한다면 length 뿐 아니라 여러가지 정보도 클래스에 함께 넣어 줄 수 있다. 어차피 파이썬의 리스트형도 실제는 리스트가 아니라 배열처럼 사용하고 있다.
파이썬 설계자의 취지가 궁굼하면 import this 를 읽어보는 것을 추천한다.
*데이터 추가하기
실제로 동적 타이프가 작동하는 것은 여기서 부터다. 들어오는 data 가 무엇인지 실행시간에 알아낸다.
일반적으로 정수형이라고 가정하고 작성한 메서드다. 앞쪽에 넣는 방법과 뒤쪽으로 넣는 방법이 있다.
포인터를 어떻게 연결시키느냐의 차이를 생각해보고 그림을 그려보는 것이 도움이 된다.
코드만 봐서는 잘 와닿지 않는다면 꼭 그림을 그려본다.
하나의 노드에는 두개의 주소와 하나의 데이터(혹은 객체)가 들어간다.
NODE A라고 하면
- NODE A가 있는 주소
- NODE A가 가리키는 다음 주소 NODE A.next
- NODE A가 가진 데이터 NODE A.data
이 포인트를 잡고 그림을 그려보면 대부분 이해가 갈 것이다.
그리고 cur 는 탐색을 위한 노드를 말한다. 실제 값을 저장하는 노드가 아니라 탐색하는 노드이다. 노드를 자르거나 붙이는 것은 이 cur 노드를 통해서 하니 어떻게 동작하는지 그림으로 그려보는게 좋다.
배열을 for 문의 index 로 루프하지만 링크드리스트는 참조를 타고 넘어간다. while 루프에서 cur = self.head 가
cur.next 라는 것은 self.head.next 헤드에서 다음 다음에 있는 노드를 가리키는 것이다. cur는 탐색 노드기 때문에 cur = cur.next 문장을 반복할 수록 뒤로 넘어간다. 마지막 노드는 cur.next == None 상태 체크로 끝날 것이다. 이 상태에서 한번 더 cur = cur.next 를 실행하면 접근 범위를 초과하는 오류가 일어난다. C언어는 바로 메모리를 건드려서 이상 종료가 되지만 파이썬은 Excetion 을 발생시켜 종료한다. 이 내용을 알고 있으면 자유자재로 이동할 수 있을 것이다. 이 과정을 IT용어로 traverse(횡단하다) 라고 한다.
노드를 추가하는 함수를 호출하면 현재 노드의 상황이 어디있는지 파악하는 것이 첫번째고 마지막에 어떤 상태에서 종료되는지 생각해야한다. 정상적으로 종료할 수 있도록 한다. 시작과 끝이 중요하다.
* 노드를 생성하고 추가하는 것을 할 수 있다면 나머지는 비슷한 과정의 반복이다. 순서가 조금 바뀌거나 방향이 바뀌는 정도의 제어로도 구현할 수 있다. 아래 전체 소스코드를 참고한다.
* 파이썬의 경우 C언어 처럼 메모리 해제를 직접하지 않아도 된다. 자바 JVM 처럼 GC(가비지 콜렉터)가 객체의 카운터가 0이되면 알아서 삭제하거나. 스크립트가 끝나면 삭제된다. 언제 소멸되는지 궁굼하다면 클래스의 __del__ 을 사용해서 확인해본다. 객체의 카운터를 0으로 만드는 부분은 고급 주제이다. 이 포스팅에서는 다루지 않지만 언젠가 필요할지도 모르니 공부해두면 좋다.
* 전체 소스코드
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
class LinkedList():
def __init__(self):
print("-> Linked List constructed...")
self.head = None
self.length = 0
def __del__(self):
print("instance deleted...")
# add first 앞쪽에 넣기
def addFirst(self, data):
node = Node(data)
node.next = self.head
self.head = node
self.length += 1
# add last 뒤쪽에 넣기
def append(self, data):
cur = self.head
# 비어있는 경우
if cur == None:
self.addFirst(data)
return
# 추가하는 경우
newNode = Node()
newNode.data = data
while cur.next != None:
cur = cur.next
cur.next = newNode
self.length += 1
print("- append suceeded!")
def showList(self):
print('*instance ID show list', self)
print("[", end='')
node = self.head
while node:
print(node.data, end=', ')
node = node.next
print("]")
print('*list length:', self.length)
# index 값으로 삭제
def deleteNode(self, index):
prev = None
cur = self.head
index -= 1
i = 0
while cur.next != None and i < index:
prev = cur
print(cur.data, index)
cur = cur.next
i += 1
if index == i:
self.length -= 1
if prev == None:
self.head = cur.next
else:
prev.next = cur.next
else:
print('index out of range...')
def searchByKey(self, key):
index = 0
cur = self.head
while cur != None:
if cur.data == key:
print("found match! [", key, "] at index: ", index)
return
cur = cur.next
index += 1
print('*no match key : ',key)
def main():
print('[파이썬 링크드 리스트 구현]')
print('1. 노드생성')
myLList = LinkedList()
myLList.append(999)
myLList.addFirst(1)
myLList.addFirst(2)
myLList.addFirst(3)
myLList.addFirst(4)
myLList.showList()
myLList.append(5)
myLList.append(6)
myLList.append(7)
myLList.showList()
myLList.deleteNode(1)
myLList.deleteNode(1)
myLList.deleteNode(1)
myLList.showList()
myLList.searchByKey(7)
listA = "양양이"
newList = LinkedList()
newList.append(listA)
newList.showList()
if __name__ == '__main__':
main()
