[파이썬 자료구조] 파이썬으로 연결 리스트 구현하기

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

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

 

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

 

 

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

 

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 부분 함수가 눈에 띄게 간결하게 표현된 것을 확인 할 수 있습니다.