이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.

잔재미코딩 소식 공유

좀더 제약없이, IT 컨텐츠를 공유하고자, 자체 온라인 강의 사이트와 유투브 채널을 오픈하였습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다

● 직운영 온라인 강의 서비스 오픈

● 잔재미코딩 유투브 오픈 [구독해보기]

3. 대표적인 데이터 구조2: 링크드 리스트 (Linked List)¶

배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원

본래 배열과 링크드 리스트의 장단점 (전통적인 C언어에서의 배열과 링크드 리스트)¶

본래 배열은 사전에 데이터 공간을 할당하고, 데이터를 순차적으로 저장, 인덱스와 1:1로 가리킬 수 있음
링크드 리스트는 사전에 데이터 공간을 미리 할당하지 않아도 됨
- 데이터가 필요할 때마다, 새로운 공간에 데이터를 만들고, 화살표로 기존 데이터 리스트와 연결하면 됨
파이썬은 리스트 타입이 모든 기능 지원

링크드 리스트가 어떻게 구현되는지만 알아보자¶

기본 자료 구조 이므로 알아두어야 함

링크드 리스트 기본 구조 (출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)
하나의 데이터는 해당 데이터와 화살표 정보를 가지는 노드에 저장됨

No description has been provided for this image

In [52]:

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

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

In [55]:

head = Node(10)
add(11)

print (head.data)
print (head.next.data)

10
11

In [49]:

node1.data

Out[49]:

In [50]:

head = Node(10)

파이썬으로 초간단 구현해보기¶

In [45]:

# 노드 클래스 만들기
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

In [46]:

# 데이터 생성
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)

In [47]:

# 데이터 연결하기
node1.next = node2
node2.next = node3
node3.next = node4

In [48]:

# 데이터 출력하기
node = node1
while node:
    print (node.data)
    node = node.next

링크드 리스트 기본 기능: 기존 리스트에 데이터 추가시 (출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)¶

단순하게 생각해보면 다음과 같이 작성하면 됨¶

In [56]:

# 새로운 데이터가 있을때
node5 = Node(2)

In [74]:

# 중간에 껴넣기 (node2 와 node3 사이)
node2.next = node5
node5.next = node3

In [49]:

# 데이터 출력하기
node = node1
while node:
    print (node.data)
    node = node.next

객체지향 프로그래밍으로 생각해보면 다음과 같이 작성할 수 있음 (복잡)¶

In [9]:

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

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 desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next

In [10]:

node_mgmt = NodeMgmt(0)
node_mgmt.desc()

In [11]:

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

특정 노드를 삭제한다면 다음과 같이 작성할 수 있음 (복잡)¶

다음 코드는 위의 코드에서 delete 메서드만 추가한 것이므로 해당 메서드만 확인하면 됨

In [36]:

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

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 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:                   # 경우의 수1: self.head를 삭제해야할 경우 - self.head를 바꿔줘야 함
            temp = self.head                         # self.head 객체를 삭제하기 위해, 임시로 temp에 담아서 객체를 삭제했음
            self.head = self.head.next               # 만약 self.head 객체를 삭제하면, 이 코드가 실행이 안되기 때문!
            del temp
        else:
            node = self.head
            while node.next:                         # 경우의 수2: self.head가 아닌 노드를 삭제해야할 경우
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next       # 오마이갓 - 어쩔 수 없었음, 더 쉽게 작성하려 해도... node의 next 주소를 
                    del temp                         #          다다음 노드로 가리키려 하다보니 node.next의 next 로 표현해야함
                    pass                             
                else:
                    node = node.next

테스트를 위해 1개 노드를 만들어 봄¶

In [37]:

node_mgmt = NodeMgmt(0)
node_mgmt.desc()

node_mgmt.head 객체가 살아있음을 확인¶

In [38]:

node_mgmt.head

Out[38]:

<__main__.Node at 0x10b2887b8>

node_mgmt.head 를 지워봄(위에서 언급한 경우의 수1)¶

In [39]:

node_mgmt.delete(0)

다음 코드 실행시 아무것도 안나온다는 것은 node_mgmt.head 가 정상적으로 삭제되었음을 의미¶

In [40]:

node_mgmt.head

다시 하나의 노드를 만들어봄¶

In [41]:

node_mgmt = NodeMgmt(0)
node_mgmt.desc()

이번엔 여러 노드를 더 추가해봄¶

In [42]:

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

노드 중에 한개를 삭제함 (위에서 언급한 경우의 수2)¶

In [43]:

node_mgmt.delete(4)

특정 노드가 삭제되었음을 알 수 있음¶

In [44]:

node_mgmt.desc()

프로그래밍 연습
위 코드에서 node2를 삭제하고, 전체 링크드 리스트 순서 유지하기 (실제 출력해보기)

프로그래밍 연습
위 코드에서 node의 data가 특정 숫자인 것을 찾는 함수 만들기

In [51]:

def search_node(data):
    node = node1
    while node:
        if node.data == data:
            return node
        else:
            node = node.next

node = search_node(4)
print (node.data)

프로그래밍 연습
위 코드에서 새로운 값을 가지는 node를 링크드 리스트 맨 마지막에 추가하는 함수 만들고 5 값을 가지는 node 를 링크드 리스트에 추가하기

더블 링크드 리스트(Doubly linked list) 기본 구조 (출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)
- 이중 연결 리스트라고도 함
- 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능

In [98]:

# 노드 클래스 만들기
class Node:
    head = None
    
    def __init__(self, data, prev=None, next=None):
        self.prev = prev
        self.data = data
        self.next = next

def add(data):
    node = Node.head

    while node:
        prev = node
        node = node.next
    
    prev.next = Node(data)
    prev.next.prev = prev

In [99]:

Node.head = Node(0)

In [100]:

for index in range(1, 10):
    add(index)

In [101]:

Node.head.data

Out[101]:

프로그래밍 연습
위 클래스를 기반으로 새로운 노드를 더블링크드리스트에 추가하는 함수 만들고, 1 ~ 10 까지 값을 가지는 노드를 순서대로 연결하기

프로그래밍 연습
위 클래스를 기반으로 특정 값을 가지는 노드를 더블링크드리스트에서 제거하는 함수 만들고 7 값을 가진 노드를 제거하기

합리적인 분들과 확연히 다른 좋은 IT 강의를 만들 수 있는 선순환 시스템을 지향합니다