Data Structure

자료구조 - 링크드 리스트

choisanghyun 2022. 1. 8. 17:25

728x90

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

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

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

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

일반적인 링크드 리스트 형태 -->노드(데이터 + 주소(포인터)) (출처: 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 

In [2]:

class Node: #클래스로 노드 만들어야함 (속성 부여)
    def __init__(self, data, next=None): #속성 next=None -> 마지막 노드
        self.data = data #데이터
        self.next = next #주소

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

In [3]:

node1 = Node(1) #node1 = Node(데이터 =1)
node2 = Node(2) #node2 = Node(데이터 =2)
node1.next = node2  #(노드 연결하기 node1.next(주소값)==node2)
head = node1 #맨 앞 노드 표시

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

In [6]:

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

def add(data): #데이터 추가
    node = head #헤드 노드 찾기
    while node.next: # 헤드 노드부터 node.next를 타고 마지막 노드(next=none)까지 불러오기
        node = node.next 
    node.next = Node(data) #next=none에 데이터담긴 노드 연결

In [7]:

node1 = Node(1)
head = node1
for index in range(2, 10):
    add(index)  #2부터 10까지 각 노드에 데이터 추가

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

In [10]:

node = head #헤드 노드 지정
while node.next: #next=none(마지막노드)까지 노드.데이터 출력하고 넘어가기
    print(node.data)
    node = node.next
print (node.data)

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

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

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

링크드 리스트는 유지 관리에 부가적인 구현이 필요함
각 노드마다 주소로 연결되어 있기 때문에 중간에 데이터를 삭제/변경시 앞뒤 노드의 구성을 바꿔야함

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

In [11]:

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

In [12]:

node3 = Node(1.5) #1,2사이에 넣을 노드

In [13]:

node = head
search = True
while search:
    if node.data == 1:
        search = False #노드 데이터가 1이면 while문이 끝남
    else:
        node = node.next #노드 데이터가 1이 아니면 계속 다음 노드 탐색

node_next = node.next #while문으로 찾은 데이터가 1인 노드의 next를 변수에 저장 
node.next = node3 #노드(1)과 노드(1.5)를 연결
node3.next = node_next #저장한 변수(노드(1).next)를 1.5 노드의 주소값으로 연결

In [14]:

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

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

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): #add함수를 여기에다가
        if self.head == '': #방어코드
            self.head = Node(data) #헤드가 없으면 노드를 만들어서 추가
        else:
            node = self.head
            while node.next: #마지막 노드까지 탐색하고 마지막 노드에 새 노드를 next로 연결 
                node = node.next
            node.next = Node(data)
        
    def desc(self): #전체 노드 데이터 출력
        node = self.head
        while node: #노드.next==none(마지막 노드)일때까지 출력
            print (node.data)
            node = node.next

In [16]:

linkedlist1 = NodeMgmt(0) #0을 헤드로 설정
linkedlist1.desc()

In [17]:

for data in range(1, 10): #1~9까지 데이터 추가
    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): #add함수를 여기에다가
        if self.head == '': #방어코드
            self.head = Node(data) #헤드가 없으면 노드를 만들어서 추가
        else:
            node = self.head
            while node.next: #마지막 노드까지 탐색하고 마지막 노드에 새 노드를 next로 연결 
                node = node.next
            node.next = Node(data)
        
    def desc(self): #전체 노드 데이터 출력
        node = self.head
        while node: #노드.next==none(마지막 노드)일때까지 출력
            print (node.data)
            node = node.next
    
    def delete(self, data): 
        # 경우의 수 고려
        #1.헤드 삭제한 경우 -> 헤드를 바꿔줌 
        #2.마지막 노드 삭제한 경우 -> 그 전 노드의 next값 none으로 바꿔줘야함
        #3.중간 노드를 삭제한 경우 -> 삭제한 노드를 제외한 노드들 다시 연결해줘야함
        if self.head == '': #방어 코드 #값이 없을 경우
            print ("해당 값을 가진 노드가 없습니다.")
            return
        
        if self.head.data == data: # 1.헤드를 삭제할 경우(delete(data)==head.data)
            temp = self.head #밑에 self.head를 재정의 하기 때문에 객체를 삭제하기 위한 임시 변수에 저장
            self.head = self.head.next #헤드를 다음주소(next)인 노드로 바꿔줌
            del temp #삭제
        else: #헤드 데이터가 삭제할 데이터가 아닌경우 (2,3번 경우)
            node = self.head 
            while node.next: #next를 통해 노드를 탐색
                if node.next.data == data: #노드의 다음 데이터가 삭제할 데이터인경우 (삭제 대상의 바로 전 노드로 들어간다)
                    temp = node.next #다음 노드를 삭제하기 위해 변수에 담는다
                    node.next = node.next.next #다다음 노드로 연결 (삭제 대상이 마지막 노드면 none값이 됨)
                    del temp #next노드 삭제(다음 노드 삭제)
                    return
                else:
                    node = node.next

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

In [19]:

linkedlist1 = NodeMgmt(0)
linkedlist1.desc()

head 가 살아있음을 확인¶

In [20]:

linkedlist1.head

Out[20]:

<__main__.Node at 0x1099fc6a0>

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

In [21]:

linkedlist1.delete(0)

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

In [22]:

linkedlist1.head

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

In [23]:

linkedlist1 = NodeMgmt(0)
linkedlist1.desc()

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

In [24]:

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

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

In [25]:

linkedlist1.delete(4)

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

In [26]:

linkedlist1.desc()

In [27]:

linkedlist1.delete(9)

In [28]:

linkedlist1.desc()

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

In [ ]:

node_mgmt.delete(2)
node_mgmt.desc()

연습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) 기본 구조
- 이중 연결 리스트라고도 함
- 다음(next) 주소로만 연결된 링크드 리스트와 달리 이전 주소도 연결
- 이전 주소도 존재하기 때문에 마지막 노드부터 역방향 검색 가능(시간복잡도 줄이기)
- 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
  (출처: 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): #head는 시작 tail은 끝
        self.head = Node(data)
        self.tail = self.head #뒤에서부터도 검색 가능하기 떄문에 tail도 추가 <기준점>

    def insert(self, data):
        if self.head == None: #헤드가 없으면
            self.head = Node(data) #헤드 만들기
            self.tail = self.head #테일도 같은 값으로 만듬 (노드 하나면 헤드==테일) 
        else:
            node = self.head #헤드가 존재하면
            while node.next: #헤드부터 마지막 노드까지 next 계속 탐색
                node = node.next
            new = Node(data) #추가할 데이터를 가진 노드 변수에 저장 
            node.next = new #반복문이 끝나면 node는 마지막 노드를 가리킴 new(추가데이터)를 next로 연결
            new.prev = node #new의 테일부분을 마지막 노드와 연결
            self.tail = new #마지막 노드를 가리키는 tail도 추가된 노드로 변경해줘야함

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

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 #False 반환
    
        node = self.head
        while node:
            if node.data == data: #원하는 데이터면
                return node #노드 리턴
            else:
                node = node.next #원하는 데이터가 아니면 next 탐색
        return False  #탐색 다해도 없으면 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 #next를 prev로 바꾸기만하면 됨
        return False
    
    def insert_before(self, data, before_data): #넣을 데이터, 그 뒤 데이터
        if self.head == None: #헤드가 없으면
            self.head = Node(data) #노드 만들기
            return True #데이터 입력되었는지 확인을 위해서 True값 반환
        else: #헤드가 있으면
            node = self.tail #테일부터 검색
            while node.data != before_data: #before_data를 찾을 때까지
                node = node.prev #이전주소로 검색
                if node == None: #before_data가 없으면
                    return False #False값 반환
            #반복문 벗어난거면 before_data를 찾은 것임
            new = Node(data) #넣을 데이터 변수에 담기
            before_new = node.prev #before_data의 바로 전 데이터
            before_new.next = new #before_data의 바로 전 데이터를 new와 next로 연결
            new.prev = before_new #new와 before_data의 바로 전 데이터를 prev로 연결
            new.next = node #new.next로 before_data를 연결
            node.prev = new #before_data와 new.next를 prev로 연결
            return True #입력했으니 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]:

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