파이썬으로 연결 리스트 구현하기

파이썬으로 연결 리스트 구현하기

연결 리스트는 여러개의 노드들을 순서대로 연결한 리스트를 말합니다.

예를 들어 첫번째 노드에는 첫번째 노드에 담긴 정보와 그 다음 노드에 대한 정보가 담겨 있고 그 다음 노드 역시 자기 자신에 담긴 정보와 그 다음 노드에 대한 정보가 담겨 있습니다.

이 연결 리스트는 배열과 비슷한 듯 다른 점을 지니고 있습니다.

연결 리스트를 파이썬 코드로 구현하면 다음과 같이 구현 할 수 있습니다.

class Node: def __init__(self, item): self.data = item self.next = None class LinkedList: def __init__(self): self.nodeCount = 0 self.head = None self.tail = None def __repr__(self): if self.nodeCount == 0: return 'LinkedList: empty' s = '' curr = self.head while curr is not None: s += repr(curr.data) if curr.next is not None: s += ' -> ' curr = curr.next return s # 연결 리스트에 특정 요소를 찾는 메소드 -> 특정 원소 참조 # 몇번째 있는 노드를 찾을 것인지 위치를 입력 받고 # pos 번째에 있는 노드 전체를 리턴한다. def getAt(self, pos): if pos < 1 or pos > self.nodeCount: return None i = 1 curr = self.head # 초기 node 위치 저장 while i < pos: curr = curr.next # 다음 node 위치 저장 i += 1 return curr # 연습 문제 연결리스트 순회 def traverse(self): lst=[] if self.nodeCount==0: return [] else: curr = self.head i=1 while i<=self.nodeCount: lst.append(curr.data) curr = curr.next i+=1 return lst # 연결 리스트 길이 알기 def getLength(self): return self.nodeCount # 연결리스트 원소 삽입 def insertAt(self, pos, newNode): if pos < 1 or pos > self.nodeCount + 1: return False if pos == 1: newNode.next = self.head self.head = newNode else: if pos == self.nodeCount + 1: prev = self.tail else: prev = self.getAt(pos - 1) # 집어넣을 위치 이전 요소를 찾는다. newNode.next = prev.next # 새로 넣을 요소 다음 요소 주소에 집어넣을 위치 이전 요소에 # 입력되어 있던 다음 요소 주소를 넣는다. prev.next = newNode # 이전 요소 다음 요소 주소에 새로운 요소를 넣는다. if pos == self.nodeCount + 1: self.tail = newNode self.nodeCount += 1 return True # 두 연결 리스트 합치기 def concat(self,L): self.tail.next = L.head if L.tail: # L리스트가 비어있지 않은 경우를 제외한다. self.tail = L.tail self.nodeCount += L.nodeCount # 특정 노드 지우기 def popAt(self,pos): data=0 if pos <1 or pos>self.nodeCount: raise IndexError if pos ==1: if pos==self.nodeCount: curr=self.head self.head=None self.tail=None data=curr.data else: curr=self.head self.head=curr.next data=curr.data else: if pos==self.nodeCount: prev=self.getAt(pos-1) curr=prev.next prev.next=None self.tail=prev data=curr.data else: prev=self.getAt(pos-1) curr=prev.next prev.next=curr.next data=curr.data self.nodeCount-=1 return data

이런 식으로 연결 리스트에 특정 노드 삽입, 제거, 연결 리스트 순회, 두개의 연결리스트 이어 붙이기, 특정 노드 위치 찾기 등을 할 수 있습니다.

L=LinkedList() a=Node(38) b=Node("안녕") c=Node([1,2,3]) L.insertAt(1,a) print(L) L.insertAt(1,b) print(L) L.insertAt(2,c) print(L) L.popAt(2) print(L) ''' 출력 결과 '안녕' -> 38 '안녕' -> [1, 2, 3] -> 38 '안녕' -> 38 '''

비어있는 연결리스트에 이렇게 문자와 숫자, 그리고 리스트도 들어가는 것을 확인할 수 있습니다.

이러한 연결리스트는 0번째 연결 리스트에 dummy head를 설정해두고

node 추가 혹은 제거 시 insertnext, potnext 함수를 따로 설정하여 좀더 간편하게 연결리스트 코드를 작성할 수 있습니다.

class Node: def __init__(self, item): self.data = item self.next = None class LinkedList: def __init__(self): self.nodeCount = 0 self.head = Node(None) self.tail = None self.head.next = self.tail def traverse(self): result = [] curr = self.head while curr.next: curr = curr.next result.append(curr.data) return result def getAt(self, pos): if pos < 0 or pos > self.nodeCount: return None i = 0 curr = self.head while i < pos: curr = curr.next i += 1 return curr def insertAfter(self, prev, newNode): newNode.next = prev.next if prev.next is None: self.tail = newNode prev.next = newNode self.nodeCount += 1 return True def insertAt(self, pos, newNode): if pos < 1 or pos > self.nodeCount + 1: return False if pos != 1 and pos == self.nodeCount + 1: prev = self.tail else: prev = self.getAt(pos - 1) return self.insertAfter(prev, newNode) def popAfter(self, prev): curr=prev.next prev.next=curr.next if curr.next==None: self.tail=prev self.nodeCount-=1 return curr.data def popAt(self, pos): if pos<1 or pos>self.nodeCount: raise IndexError if pos==1: prev=self.head else: prev=self.getAt(pos-1) return self.popAfter(prev)

다른 부분은 크게 차이나지 않지만 요소를 추가하는 insert 부분과 제거하는 pop 부분 함수가 눈에 띄게 간결하게 표현된 것을 확인 할 수 있습니다.

from http://polarmin.tistory.com/7 by ccl(A) rewrite - 2021-08-19 16:26:06