[자료구조] : 링크드 리스트(Linked List) - 단순연결리스트(Singly linked list)

링크드 리스트(Linked List) - 단순연결리스트(Singly linked list)
- 연결 리스트라고도 한다.

- 배열(Array)
    → 장점 : 빠르게 접근이 가능하다.

    → 단점 : 메모리 사용이 비 효율적
                   배열 내의 공간을 미리 확보하여 구성하므로 데이터를 추가로 넣기 어렵다.

- 연결리스트(Linked List)
- 링크드 리스트는 떨어진 곳에 존재하는 데이터를 포인터로 연결해, 관리하는 데이터 구조
- 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원 한다.

    → 장점 : 삽입과 삭제가 편하다.
                  사용 후 메모리의 재사용이 가능하다.
                  메모리 공간을 미리 할당하지 않아도 되어 데이터를 추가, 제거, 등이 편하다.

    → 단점 : 포인터의 사용으로 저장공간 또한 추가로 사용한다.
                  알고리즘이 복잡하다.
                  특정 자료의 탐색 시간이 많이 소요된다.
                  중간에 데이터를 삽입, 삭제시 노드 연결을 재 구성해야한다.

- 용어
    → 노드(Node) : 데이터 저장 단위 (데이터값, 포인터)로 구성
    → 포인터(Pointer) : 각 노드 안에서 다음, 이전의 노드와 연결 주소를 가지고 있는 공간
    → head : 가장 첫 번째 노드
    → tail : 가장 마지막 노드

    → get_all() : 모든 노드의 데이터 가져오기
    → get_Node() : 인덱스에 해당하는 노드 가져오기
    → append_() : 기존 Tail 노드에 새 노드 추가
    → insert_() : 기존 인덱스에 새 노드 삽입
    → delete() : 인덱스에 해당하는 노드 제거

 

Singly Linked List 

append_() :
연결리스트에 노드가 추가될 때

새로운 노드 생성

Tail 노드의 porinter가 가리키는 값이 새로운 노드의 주소로 바뀌며, 새로운 노드의 pointer는 None을 가리킨다.

insert_() :
연결리스트의 특정 위치에 노드가  추가될 때

새로운 노드 생성

추가될 특정 위치의 이전 노드 pointer가 가리키는 값이 새로운 노드의 주소로 바뀌며, 새로운 노드의 pointer는 이전 노드가 가리키던 노드를 가리킨다.

delete() :
연결리스트의 특정 위치의 노드가  제거될 때

특정 위치의 노드가 제거될 때

제거될 특정 위치의 노드 pointer가 가리키는 값을 제거될 이전 노드 pointer가 가리키며, 특정 위치의 노드는 제거된다.

 

 

---

Python 구현

class Node:
    """
    파이썬으로 Node 구현
    ---------------------
    """
    def __init__(self, data):
        self.data = data
        self.pointer = None

 

class SinglyLinkedList:
    """
    파이썬으로 단순 연결리스트 구현
    -------------------------------

    get_all : 모든 노드 데이터 가져오기

    get_Node : 인덱스에 해당하는 노드 가져오기
    
    append_ : 기존 Tail 노드에 새 노드 추가
    
    insert_ : 기존 인덱스에 새 노드 삽입
    
    delete : 인덱스에 해당하는 노드 삭제
    """
    def __init__(self, data):
        """
        Head 노드 생성
        """
        self.head = Node(data)

    def get_all(self):
        cursor = self.head
        while cursor != None:
            print(cursor.data)
            cursor = cursor.pointer
            
    def get_Node(self, index_):
        """
        return 노드
        
        index_ : 노드 인덱스
        """
        cursor = self.head
        count_ = 0
        while index_ > count_:
            count_ += 1
            cursor = cursor.pointer
        return cursor
    
    def append_(self, data):
        """
        return None
        
        data : 추가할 데이터
        """
        cursor = self.head
        while cursor.pointer is not None:
            cursor = cursor.pointer
        cursor.pointer = Node(data)
        
    def insert_(self, index_, data):
        """
        return None
        
        index_ : 노드 인덱스
        
        data : 삽입할 데이터
        """
        insert_Node = Node(data)
        if index_ == 0:
            insert_Node.pointer = self.head
            self.head = insert_Node
            return
        cursor = self.get_Node(index_-1)
        next_cursor = cursor.pointer
        cursor.pointer = insert_Node
        insert_Node.pointer = next_cursor
        
    def delete(self, index_):
        """
        return None
        
        index_ : 노드 인덱스
        """
        delete_Node = self.head
        if index_ == 0:
            self.head = self.head.pointer
            return
        cursor = self.get_Node(index_-1)
        cursor.pointer = cursor.pointer.pointer
        del delete_Node

 

# singly linked list(node head)생성
data = SinglyLinkedList('F')

 

→ get_all()를 사용하여 Singly Linked List의 모든 노드 데이터값 확인

#  get_all()을 사용하여 생성된 singly linked list안의 모든 노드 값 출력
data.get_all()

F

 

→ append_()를 사용하여 생성된 Singly Linked List에 노드 추가

# 생성된 singly linked list에 노드 추가
for i in '7 prj':
    data.append_(i)

 

→ get_all()를 사용하여 Singly Linked List의 모든 노드 데이터값 확인

#  get_all()을 사용하여 생성된 singly linked list안의 모든 노드 값 출력
data.get_all()

F
7
 
p
r
j

 

 

→ insert_()를 사용하여 생성된 Singly Linked List의 특정 위치에 노드 추가

# 특정 인덱스에 노드 넣기
data.insert_(5, 'o')

 

→ get_all()를 사용하여 Singly Linked List의 모든 노드 데이터값 확인

#  get_all()을 사용하여 생성된 singly linked list안의 모든 노드 값 출력
data.get_all()

F
7
 
p
r
o
j

 

→ delete()를 사용하여 생성된 Singly Linked List의 특정 위치의 노드 제거

# 특정 인덱스 노드 제거
data.delete(5)

 

→ get_all()를 사용하여 Singly Linked List의 모든 노드 데이터값 확인

#  get_all()을 사용하여 생성된 singly linked list안의 모든 노드 값 출력
data.get_all()

F
7
 
p
r
j