링크드 리스트 (Linked List) (2)

앞서 알아본 링크드 리스트(Linked List)에 대해 조금 더 깊이 알아보겠다.

 

4. 링크드 리스트 데이터 사이에 데이터를 추가

링크드 리스트는 유지 관리에 부가적인 구현이 필요하다.

 

wikipedia, https://en.wikipedia.org/wiki/Linked_list

 

위 그림을 보면, 원래 데이터 값이 12인 노드는 데이터 값이 99인 노드를 가리키고 있다. 그런데 데이터 값이 37인 새로운 노드가 이 두 노드 사이에 들어가려고 하면, 원래 99를 가리키고 있던 12는 37을 가리켜야 하고, 추가된 노드인 37은 99를 가리켜야 한다. 부가적인 구현이 필요한 것이다.

 

링크드 리스트 데이터 사이에 데이터를 추가하는 코드를 만들어보면,

 

node = head	# 노드에 헤드값 넣기
search = True
while search:
    if node.data == 1:	# 데이터 값이 1인 노드 바로 뒤에 새로운 노드를 추가하고 싶을 때
        search = False
    else:
        node = node.next	# 아직 못 찾았으면 다음 노드로 이동

node_next = node.next	# 새로운 노드 다음 노드 위치를 node_next에 임시 저장
node.next = newNode	# 새로운 노드인 newNode를 가리키도록 설정
newNode.next = node_next	# 새로운 노드인 newNode가 전 노드가 가리키는 곳을 가리키도록 설정

 

이렇게 된다. 가령 데이터 값이 1.5인 노드를 새롭게 만들어 데이터 값이 1과 2인 노드들 사이에 추가하고 싶다면,

 

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

# 첫 번째 노드 생성 및 head에 첫 번째 노드 값 담기
node1 = Node(1)
head = node1

def add(data):
    node = head
    while node.next:
        node = node.next
    node.next = Node(data)

# 첫 번째 노드에 2~9의 노드 추가하기
for index in range(2, 10):
    add(index)

# 새로운 노드 newNode 생성
newNode = Node(1.5)

# 데이터 사이에 새 노드 추가
node = head
search = True
while search:
    if node.data == 1:
        search = False
    else:
        node = node.next

node_next = node.next
node.next = newNode
newNode.next = node_next

# 출력
node = head
while node.next:
    print(node.data)
    node = node.next
print(node.data)

 

이렇게 되고,

 

 

이렇게 출력된다.

 

5. 파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기

파이썬 객체지향을 활용해, NodeMgmt라는 클래스를 만들어 데이터 추가, 출력 등의 작업을 수월하게 할 수 있다.

 

코드로 구현하면,

 

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
    
class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        
    def add(self, data):	# 해당 링크드 리스트의 맨 끝에 노드 추가하는 함수
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
            
    def middleAdd(self, prevData, addData):	# 해당 링크드 리스트의 중간에 값을 추가하는 함수
        node = self.head
        while node:
            if node.data == prevData:
                break
            else:
                node = node.next
        if node is None:
            print("해당 연결 리스트에는 찾으시는 노드가 존재하지 않습니다.")
            return

        newNode = Node(addData)
        node_next = node.next
        node.next = newNode
        newNode.next = node_next
        
    def desc(self):	# 전체 데이터 출력하는 함수 (description)
        node = self.head
        while node:
            print (node.data)
            node = node.next

 

이렇게 해서 객체를 만들고 쉽게 관리할 수 있다.

 

linkedlist1 = NodeMgmt(0)

for data in range(1, 10):
    linkedlist1.add(data)
    
linkedlist1.desc()

 

이렇게 하면 0~9까지 생성된 노드가 출력되는 것이다.

 

5. 특정 노드를 삭제

링크드 리스트에서 특정 노드를 삭제하는 것은 세 가지 경우의 수가 있다.

1. head 삭제
2. 마지막 노드 삭제
3. 중간 노드 삭제

우선, head를 삭제하는 경우 맨 앞의 노드를 삭제하고 그 다음 노드를 head로 지정하면 된다. 마지막 노드를 삭제하는 경우, 마지막 노드를 삭제하고 직전 노드가 가리키는 곳을 None(null)로 하면 된다. 중간에 있는 노드를 삭제할 때에는, 삭제하고자 하는 노드의 직전 노드가 삭제하고자 하는 노드의 바로 다음 노드를 가리키게 하고, 삭제 작업을 진행하면 된다.

 

특정 노드를 삭제하는 코드는 다음과 같다.

 

def delete(self, data):
        if self.head == '':	# head가 없는, 즉 링크드 리스트가 텅 비어 있는 상황
            print ("해당 값을 가진 노드가 없습니다.")
            return
        
        if self.head.data == data:	# head 삭제
            temp = self.head	# temp라는 변수에 임시로 head 값 저장
            self.head = self.head.next	# 원래 head의 다음 노드를 head로 지정
            del temp	# 저장공간 관리를 위해 지우고자 했던 헤드(temp) 삭제
        else:	# 마지막 노드, 중간 노드 삭제는 이 코드로 한꺼번에 관리할 수 있다.
            node = self.head
            while node.next:
                if node.next.data == data:	# 중간이든 마지막이든 지우고 싶은 값을 가진 노드가 있을 때
                    temp = node.next
                    node.next = node.next.next	# 마지막 노드 삭제하는 경우, 어차피 null(None) 가리키게 하면 사라지는 것은 동일하다.
                    del temp
                    return
                else:
                    node = node.next

 

특이한 점은 중간에 있는 노드를 삭제하는 것과, 마지막 노드를 삭제하는 부분은 통합 관리할 수 있다는 것이다. node.next = node.next.next을 사용함으로써, 중간 노드를 삭제한다면 실재하는 다음 노드를 직전 노드가 가리키게 하는 것이고, 마지막 노드를 삭제한다면 실재하지 않는 다음 노드인 None(null) 값을 직전 노드가 가리키게 하는 것이다.

 

테스트를 위해서 앞서 작성한 NodeMgmt 클래스를 이용해 링크드 리스트 객체를 생성하고 삭제 작업을 수행해보면,

 

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
    
class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        
    def add(self, data):
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
            
    def middleAdd(self, prevData, addData):
        node = self.head
        while node:
            if node.data == prevData:
                break
            else:
                node = node.next
        if node is None:
            print("해당 연결 리스트에는 찾으시는 노드가 존재하지 않습니다.")
            return

        newNode = Node(addData)
        node_next = node.next
        node.next = newNode
        newNode.next = node_next
        
    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next
    
    # 삭제 작업
    def delete(self, data):
        if self.head == '':
            print ("해당 값을 가진 노드가 없습니다.")
            return
        
        if self.head.data == data:
            temp = self.head
            self.head = self.head.next
            del temp
        else:
            node = self.head
            while node.next:
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    return
                else:
                    node = node.next
                    

# 테스트를 위해서 1개 노드를 만들어 봄
linkedList1 = NodeMgmt(0)
linkedList1.desc()	# 0

# head가 살아있음을 확인
print(linkedList1.head)	# <__main__.Node object at 0x10310dfa0> 살아있음

# head를 지워보고 출력
linkedList1.delete(0)
print(linkedList1.head)	# None

# 다시 하나의 노드 만들고, 여러 노드 추가한 다음, 노드 중에 한 개 삭제
linkedList1 = NodeMgmt(0)
for data in range(1, 10):
    linkedList1.add(data)
    
linkedList1.delete(4)
linkedList1.desc()	# 데이터 값이 4인 노드가 삭제된 것을 알 수 있다.

 

 

이렇게 4가 성공적으로 삭제된 채 출력된다.

 

 

 

 

 

[참고문헌]

패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online 강의자료