대표적인 자료구조: 링크드 리스트

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

잔재미코딩 소식 공유

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

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

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

6. 대표적인 자료구조: 링크드 리스트 (Linked List)¶

1. 링크드 리스트 (Linked List) 구조¶

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

링크드 리스트 기본 구조와 용어
- 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성
- 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

* 일반적인 링크드 리스트 형태 No description has been provided for this image

(출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)

2. 간단한 링크드 리스트 예¶

Node 구현¶

보통 파이썬에서 링크드 리스트 구현시, 파이썬 클래스를 활용함
- 파이썬 객체지향 문법 이해 필요
- 참고: https://www.fun-coding.org/PL&OOP1-3.html

In [1]:

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

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다

데이터 분석/과학 로드맵

데이터 분석가와 데이터 과학자 직군의 기본기를 차근차근 쌓을 수 있도록 꾸몄습니다

자세히 알아보기 모든 강좌 보기

In [3]:

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

Node와 Node 연결하기 (포인터 활용)¶

In [4]:

node1 = Node(1)
node2 = Node(2)
node1.next = node2
head = node1

링크드 리스트로 데이터 추가하기¶

In [5]:

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

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

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

가장 빠르게 풀스택 개발자가 될 수 있도록, 최적화된 로드맵을 제공합니다

웹/앱서비스 풀스택 로드맵

자세히 알아보기 모든 강좌 보기

In [9]:

node1 = Node(1)
head = node1
for index in range(2, 10):
    add(index)

링크드 리스트 데이터 출력하기(검색하기)¶

In [10]:

node = head
while node.next:
    print(node.data)
    node = node.next
print (node.data)

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

장점
- 미리 데이터 공간을 미리 할당하지 않아도 됨
  - 배열은 미리 데이터 공간을 할당 해야 함
단점
- 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
- 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
- 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

4. 링크드 리스트의 복잡한 기능1 (링크드 리스트 데이터 사이에 데이터를 추가)¶

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

(출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다

데이터 분석/과학 로드맵

데이터 분석가와 데이터 과학자 직군의 기본기를 차근차근 쌓을 수 있도록 꾸몄습니다

자세히 알아보기 모든 강좌 보기

In [11]:

node = head
while node.next:
    print(node.data)
    node = node.next
print (node.data)

In [12]:

node3 = Node(1.5)

In [13]:

node = head
search = True
while search:
    if node.data == 1:
        search = False
    else:
        node = node.next

node_next = node.next
node.next = node3
node3.next = node_next

In [14]:

node = head
while node.next:
    print(node.data)
    node = node.next
print (node.data)

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

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

가장 빠르게 풀스택 개발자가 될 수 있도록, 최적화된 로드맵을 제공합니다

웹/앱서비스 풀스택 로드맵

자세히 알아보기 모든 강좌 보기

In [15]:

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

In [16]:

linkedlist1 = NodeMgmt(0)
linkedlist1.desc()

In [17]:

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

6. 링크드 리스트의 복잡한 기능2 (특정 노드를 삭제)¶

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

In [18]:

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 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

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다

데이터 분석/과학 로드맵

데이터 분석가와 데이터 과학자 직군의 기본기를 차근차근 쌓을 수 있도록 꾸몄습니다

자세히 알아보기 모든 강좌 보기

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

In [19]:

linkedlist1 = NodeMgmt(0)
linkedlist1.desc()

head 가 살아있음을 확인¶

In [20]:

linkedlist1.head

Out[20]:

<__main__.Node at 0x1099fc6a0>

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

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

가장 빠르게 풀스택 개발자가 될 수 있도록, 최적화된 로드맵을 제공합니다

웹/앱서비스 풀스택 로드맵

자세히 알아보기 모든 강좌 보기

In [21]:

linkedlist1.delete(0)

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

In [22]:

linkedlist1.head

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

In [23]:

linkedlist1 = NodeMgmt(0)
linkedlist1.desc()

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다

데이터 분석/과학 로드맵

데이터 분석가와 데이터 과학자 직군의 기본기를 차근차근 쌓을 수 있도록 꾸몄습니다

자세히 알아보기 모든 강좌 보기

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

In [24]:

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

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

In [25]:

linkedlist1.delete(4)

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

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

가장 빠르게 풀스택 개발자가 될 수 있도록, 최적화된 로드맵을 제공합니다

웹/앱서비스 풀스택 로드맵

자세히 알아보기 모든 강좌 보기

In [26]:

linkedlist1.desc()

In [27]:

linkedlist1.delete(9)

In [28]:

linkedlist1.desc()

연습1: 위 코드에서 노드 데이터가 2인 노드 삭제해보기

In [ ]:

node_mgmt.delete(2)
node_mgmt.desc()

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다

데이터 분석/과학 로드맵

데이터 분석가와 데이터 과학자 직군의 기본기를 차근차근 쌓을 수 있도록 꾸몄습니다

자세히 알아보기 모든 강좌 보기

연습2: 위 코드에서 노드 데이터가 특정 숫자인 노드를 찾는 함수를 만들고, 테스트해보기
테스트: 임의로 1 ~ 9까지 데이터를 링크드 리스트에 넣어보고, 데이터 값이 4인 노드의 데이터 값 출력해보기

In [ ]:

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       
                    del temp                         
                    pass                             
                else:
                    node = node.next
                    
    def search_node(self, data):
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next

In [ ]:

# 테스트
node_mgmt = NodeMgmt(0)
for data in range(1, 10):
    node_mgmt.add(data)

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

7. 다양한 링크드 리스트 구조¶

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

(출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)

In [2]:

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

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head

    def insert(self, data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new

    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

가장 빠르게 풀스택 개발자가 될 수 있도록, 최적화된 로드맵을 제공합니다

웹/앱서비스 풀스택 로드맵

자세히 알아보기 모든 강좌 보기

In [3]:

double_linked_list = NodeMgmt(0)
for data in range(1, 10):
    double_linked_list.insert(data)
double_linked_list.desc()

연습3: 위 코드에서 노드 데이터가 특정 숫자인 노드 앞에 데이터를 추가하는 함수를 만들고, 테스트해보기
- 더블 링크드 리스트의 tail 에서부터 뒤로 이동하며, 특정 숫자인 노드를 찾는 방식으로 함수를 구현하기
- 테스트: 임의로 0 ~ 9까지 데이터를 링크드 리스트에 넣어보고, 데이터 값이 2인 노드 앞에 1.5 데이터 값을 가진 노드를 추가해보기

In [16]:

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

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head

    def insert(self, data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new

    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next
    
    def search_from_head(self, data):
        if self.head == None:
            return False
    
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next
        return False
    
    def search_from_tail(self, data):
        if self.head == None:
            return False
    
        node = self.tail
        while node:
            if node.data == data:
                return node
            else:
                node = node.prev
        return False
    
    def insert_before(self, data, before_data):
        if self.head == None:
            self.head = Node(data)
            return True
        else:
            node = self.tail
            while node.data != before_data:
                node = node.prev
                if node == None:
                    return False
            new = Node(data)
            before_new = node.prev
            before_new.next = new
            new.prev = before_new
            new.next = node
            node.prev = new
            return True

In [17]:

double_linked_list = NodeMgmt(0)
for data in range(1, 10):
    double_linked_list.insert(data)
double_linked_list.desc()

In [15]:

node_3 = double_linked_list.search_from_tail(3)
node_3.data

Out[15]:

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다

데이터 분석/과학 로드맵

데이터 분석가와 데이터 과학자 직군의 기본기를 차근차근 쌓을 수 있도록 꾸몄습니다

자세히 알아보기 모든 강좌 보기

In [18]:

double_linked_list.insert_before(1.5, 2)
double_linked_list.desc()

In [19]:

node_3 = double_linked_list.search_from_tail(1.5)
node_3.data

Out[19]:

1.5

연습4: 위 코드에서 노드 데이터가 특정 숫자인 노드 뒤에 데이터를 추가하는 함수를 만들고, 테스트해보기
- 더블 링크드 리스트의 head 에서부터 다음으로 이동하며, 특정 숫자인 노드를 찾는 방식으로 함수를 구현하기
- 테스트: 임의로 0 ~ 9까지 데이터를 링크드 리스트에 넣어보고, 데이터 값이 1인 노드 다음에 1.7 데이터 값을 가진 노드를 추가해보기

In [ ]:

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

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head
    
    def insert_before(self, data, before_data):
        if self.head == None:
            self.head = Node(data)
            return True            
        else:
            node = self.tail
            while node.data != before_data:
                node = node.prev
                if node == None:
                    return False
            new = Node(data)
            before_new = node.prev
            before_new.next = new
            new.next = node
            return True

    def insert_after(self, data, after_data):
        if self.head == None:
            self.head = Node(data)
            return True            
        else:
            node = self.head
            while node.data != after_data:
                node = node.next
                if node == None:
                    return False
            new = Node(data)
            after_new = node.next
            new.next = after_new
            new.prev = node
            node.next = new
            if new.next == None:
                self.tail = new
            return True

    def insert(self, data):
        if self.head == None:
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new

    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next

In [ ]:

node_mgmt = NodeMgmt(0)
for data in range(1, 10):
    node_mgmt.insert(data)

node_mgmt.desc()

node_mgmt.insert_after(1.5, 1)
node_mgmt.desc()