연결 리스트(LinkedList)

연결 리스트

---

연결 리스트란?
자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조입니다. 삽입과 삭제가 유연하다는 장점이 있습니다.

기본적 연결리스트 예)

-      Node로 구성되어있으며, 한 Node는 Data와 다음의 Link로 구성되어 있습니다.
-      리스트의 맨 앞을 Head, 맨 뒤를 Tail이라고 칭합니다.

 

[Node 클래스 정의]

class Node:

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

연결리스트는 Node들로 구성되어있으므로 Node클래스를 정의합니다.
Node는 Data와 다음 노드를 가르키는 Link로 구성되어 있습니다.

 

[LinkedList 클래스 정의]

class LinkedList:

    def __init__(self):
	    self.nodeCount = 0
	    self.head = Node(None)
	    self.tail = None
	    self.head.next = self.tail


    def __repr__(self):

	    if self.nodeCount == 0:
		    return 'LinkedList: empty'

	    s = ''
	    curr = self.head
	    while curr.next:
	        curr = curr.next
		    s += repr(curr.data)
            
		    if curr.next is not None:
			    s += ' -> '
	    return s

연결리스트를 __init__이라는 함수를 통해 초기화시킵니다. 연결리스트의 사이즈를 나타낼 수 있는 속성인 nodeCount와 head를 Node클래스의 변수로, tail은 None으로, head의 다음 링크는 tail로 지정해줍니다.

 

[getAt 함수 정의]

    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

getAt(self, pos): 위치값을 인자로 받아 해당 노드를 리턴하는 함수입니다.

pos라는 인자가 0보다 작거나, 연결리스트의 사이즈보다 크다면 위치값이 유효하지 않습니다. 유효하지 않은 값이라면, None을 리턴합니다. 
i를 0으로 초기화 한뒤, curr이라는 변수에는 연결리스트의 head를 지정합니다.
해당 위치 보다 i의 값이 작을 때 동안, curr이라는 노드를 다음 노드로 넘겨가며 해당 pos위치에 있는 노드가 무엇인지 알 수 있도록 할 수 있습니다.

 

[원소의 삽입]

    # pos가 가르키는 위치에 newNode를 삽입 후, 성공/실패에 따라 T/F를 리턴
    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 insertAfter(self, prev, newNode):
		newNode.next = prev.next
		if prev.next is None:
			self.tail = newNode
		prev.next = newNode
		self.nodeCount += 1
		return True

insertAt(self, pos, newNode): pos의 위치에 newNode를 삽입 후, 성공/실패에 따라 T/F를 리턴하는 함수입니다.

pos라는 위치를 나타내는 인자와, 삽일할 노드를 인자로 받습니다.  
pos위치가 유효하지 않는다면 삽입에 실패했다는 뜻의 False를 리턴합니다.

또한, pos의 위치가 1이 아니지만, 연결리스트의 size보다 1이 더 크다면 삽입할 노드는 가장 끝에 삽입되어야 할 것이며, 이를 위해 삽입 위치의 이전 노드(prev)는 tail일 것입니다.
이런 경우가 아니라면, pos - 1 노드가 prev가 될 것입니다.

이렇게 삽입할 노드 이전의 prev 노드를 알게 되었다면, 실제로 삽입을 하는 insertAfter함수를 호출합니다.

insertAfter(self, prev, newNode): 삽입 위치 이전의 노드를 인자로 받아, 연결리스트에 원소를 삽입하는 함수입니다.

insertAt함수를 통해 이전 노드(prev)가 무엇인지 알게 되었다면, 삽입할 노드(newNode)의 next를 prev의 next로 지정합니다. 
만약 prev의 다음 노드가 없다면, prev가 tail이었을 것입니다. 그렇다면 newNode가 tail이 되겠죠?
이 경우가 아니라면, prev의 next는 newNode로 연결시켜줍니다.
하나의 노드가 삽입되었으므로, 사이즈도 커져야합니다. nodeCount를 1만큼 더해줍니다.
마지막으로 삽입이 잘 되었으므로 True를 리턴해줍니다.

 

[연결리스트의 길이]

    def getLength(self):
        return self.nodeCount

getLength(self): nodeCount의 값을 리턴해 길이를 알 수 있도록 한 함수입니다.

말그대로 연결리스트의 길이를 나타내는 nodeCount속성을 리턴해줍니다.

 

[연결리스트 순회]

    def traverse(self):
        result = []
        curr = self.head
        while curr is not None:
            result.append(curr.data)
            curr = curr.next
        return result

traverse(self): 연결리스트를 순회하는 함수입니다.

result라는 배열에 연결리스트의 순서대로 순회한 값이 들어가게됩니다. 그 결과를 리턴해주는 함수인데요.
현재 노드는 head로 잡고 시작합니다. curr이 None이 아닐 동안, result배열에 curr노드의 data값을 넣어줍니다. 
그리고 curr은 다음 노드를 가르키게 됩니다. 이렇게 순회한 값들이 모두 result에 append됩니다.

[두 리스트 합치기]

    def concat(self, L):
        self.tail.next = L.head
        if L.tail:
            self.tail = L.tail
        self.nodeCount += L.nodeCount

concat(self, L): L이라는 다른 리스트를 현재 연결리스트에 이어붙이는 함수입니다.

2개의 리스트를 이어붙이기 위해, 현재 연결리스트의 tail 노드의 next로 붙일 리스트의 head를 지정해줍니다.
붙일 리스트의 tail이 존재한다면, 현재 연결리스트의 tail을 붙일 리스트의 tail로 지정합니다.
이어 붙였기 때문에, 사이즈도 그만큼 커지게 되겠죠? 값을 더해 nodeCount값을 다시 설정합니다. 

[원소 삭제]

    def popAfter(self, prev):
        # 삭제하려는 노드를 curr에 담기
        curr = prev.next

	    # prev다음에 노드가 없는 경우 삭제할 노드가 없으니 None 리턴
        if prev.next == None:
            return None

        # 삭제할 노드 next값이 없는 경우
        if curr.next == None:
            # 유일한 노드일 때
            if self.nodeCount == 1:
                self.tail = None
            # 유일한 노드가 아닐 때
            else:
                self.tail = prev
        
        # 링크 조정
        prev.next = curr.next
        self.nodeCount -= 1
        
        return curr.data
        


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError

        prev = self.getAt(pos - 1)

        return self.popAfter(prev)

popAt(self, pos): 위치값을 인자로 받아 해당 노드를 리턴하는 함수입니다.

인자로 받는 pos(위치값)의 값이 유효하지 않을 때, IndexError를 발생시킵니다.
제거할 노드의 이전 노드(prev)를 getAt함수를 이용해 찾아냅니다.
popAfter을 호출해 실제로 노드 삭제를 하게됩니다.

popAfter(self, prev): 이전 노드를 인자로 받아 실제로 삭제를 하고, 삭제할 노드의 data를 리턴하는 함수입니다.

이전 노드(prev)를 알게 되었다면 prev.next를 통해 삭제하려는 현재 노드(curr)를 알아낼 수 있습니다.
그런데, 이때 prev의 next의 값이 지정되어있지 않다면 삭제할 노드가 없다는 뜻이므로, None을 리턴합니다.

다른 경우로는, 삭제할 노드의 next값이 None일 경우입니다. 
즉, 삭제한 노드가 tail일 때를 말하는 것입니다.
이 경우에서, 만약 nodeCount가 1이라면 삭제할 노드가 유일한 노드란 뜻이겠죠? 
tail을 None으로 설정해주어 빈 연결리스트라고 나타냅니다.
이가 아니라면, 현재 연결리스트의 tail이 prev라고 설정해줍니다.

이제, 삭제할 노드가 유일한 노드가 아니라면 prev의 next를 curr의 next로 맞춰주어야 될 것입니다.
또한, 삭제가 되었으므로 nodeCount에 1을 빼줍니다.

마지막으로 삭제한 노드의 data값을 리턴해줍니다.

 

[연결리스트 관련 전체 코드]

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 __repr__(self):

	    if self.nodeCount == 0:
		    return 'LinkedList: empty'

	    s = ''
	    curr = self.head
	    while curr.next:
	        curr = curr.next
		    s += repr(curr.data)
            
		    if curr.next is not None:
			    s += ' -> '
	    return s

    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


    # pos가 가르키는 위치에 newNode를 삽입 후, 성공/실패에 따라 T/F를 리턴
    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 getLength(self):
        return self.nodeCount


    # 연결 리스트 순회하기
    def traverse(self):
        result = []
        curr = self.head
        while curr is not None:
            result.append(curr.data)
            curr = curr.next
        return result


    # 두 리스트 합치기
    def concat(self, L):
        self.tail.next = L.head
        if L.tail:
            self.tail = L.tail
        self.nodeCount += L.nodeCount


    # 원소 삭제
    def popAfter(self, prev):
        # 삭제하려는 노드를 curr에 담기
        curr = prev.next

	    # prev다음에 노드가 없는 경우 삭제할 노드가 없으니 None 리턴
        if prev.next == None:
            return None

        # 삭제할 노드가 없는 경우
        if curr.next == None:
            # 유일한 노드일 때
            if self.nodeCount == 1:
                self.tail = None
            # 유일한 노드가 아닐 때
            else:
                self.tail = prev
        
        # 링크 조정
        prev.next = curr.next
        self.nodeCount -= 1
        
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError

        prev = self.getAt(pos - 1)

        return self.popAfter(prev)

 

 

 

 

---

참고) https://programmers.co.kr/learn/courses/57