Linked Lists

1. Linked Lists

https://stackabuse.com/python-linked-lists/

Python Linked Lists

 

연결리스트(Linked Lists)는 컴퓨터 사이언스에서 가장 흔한 데이터 구조 중 하나이다. 리스트는 참조(reference)를 통해 연결되어 있는 단일 원소들의 집합이다. 예를들어, 데이터 원소들은 address data, geographical data, geometric data, routing information, or trainsaction detsils로 구성되어 있다. 연결리스트의 각 원소들은 동일한 데이터 타입을 가지고 있다.

 

배열에 비해 추가/삭제가 용이한 점이 있지만 특정 데이터를 찾기 위해서는 순차 탐색을 하므로 탐색 속도가 느린 단점이 있다. 하지만, 연결 리스트는 '동적 할당'을 기반으로 한 리스트이기 때문에 크기를 미리 지정할 필요가 없는 장점이 있다.

 

단일 리스트 원소는 노드(node)라고 불린다. 이 노드는 값이 메모리에 연속적으로 저장되어 있는 배열과는 다르다. 대신 서로 다른 메모리 분절에서 찾을 수 있으며, 한 노드는 다른 노드에 포인터로 연결되어 있다. 마지막 노드의 포인터는 파이썬의 None으로 표시된다.

 

 

리스트에는 두가지 종류가 존재하는데, Single-linked list와 Double-linked list가 존재한다. Single-linked list에 있는 노드는 리스트의 다음 원소에만 연결이 가능하며, Double-linked list는 이전의 노드와도 연결할 수 있다. Double-linked list의 경우 데이터를 저장하기 위한 레퍼런스의 공간이 추가적으로 필요하다.

 

 

1.1 Reference

Reference(레퍼런스)는 C언어의 주소와 '비슷한' 개념으로 각각의 값들은 레퍼런스를 가지고 있으며 변수는 이 레퍼런스 값들을 따라가게 된다. 단일 연결리스트는 시작에서 끝까지 횡단이 가능하지만 반대방향으로의 횡단은 쉽지 않다. 반대로 이중 연결리스트의 경우 반대방향으로의 횡단이 가능하다.

 

단일 연결 리스트	단방향 진행	노드를 추가, 삭제시 2개의 포인터 작업 필요
이중 연결 리스트	양방향 진행	노드를 추가, 삭제시 4개의 포인터 작업 필요

 

파이썬은 연결리스트라는 내장된 데이터 타입을 가지고 있지 않기 때문에 이를 해결하기 위해선 추가적인 파이썬 모듈을 만들어야 한다.

 

2. ListNode

연결리스트 데이터 구조를 만들기 위해선 ListNode라는 이름의 클래스를 생성해야 한다. ListNode 내부에선 노드 값을 저장할 data와 list의 다음 노드를 연결할 next 클래스 변수를 생성해야 한다.

 

class ListNode : 
	def __init__(self, data) : 
    	# 연결 리스트를 초기화를 위한 함수
        # 데이터 저장
        self.data = data
        # 레퍼런스 저장
        self.next = None 
        return
        
    def has_value(self, value) : 
    	# 입력 받은 값이 노드 데이터에 존재하는지 여부 출력
        if self.data == value : 
        	return True
        else : 
        	return False

# Instanatiation of nodes
node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")

 

3. Create Single ListNode

두번째 단계는 SingleLinkedList 라는 클래스를 정의한다. SingleLinkedList는 다음과 같은 메서드를 가지고 있다.

• __init__() : 객체를 활성화 한다
• list_length() : 노드의 수를 반환한다
• output_list() : 노드 값들을 출력한다
• add_list_item() : 리스트의 끝에 노드를 추가한다
• unordered_search() : 특정한 값을 가진 리스트의 노드를 찾는다
• remove_list_item_by_id() : id에 해당되는 노드를 삭제한다

__init__() 메서드에는 클래스 내부 변수인 head와 tail이 존재하는데, head와 tail은 리스트의 시작과 끝 노드를 나타낸다.

 

class SingleLinkedList : 
	def __init__(self) : 
    	self.head = head
        self.tail = tail
        return

 

3.1 add_list_item()

SingleLinkedList 클래스의 내부에 add_list_item()을 통해 리스트에 아이템을 추가할 수 있다. 

• ListNode 클래스에 밖에 있는 객체인지를 확인한다
• item이 ListNode가 아니라면 item을 ListNode의 객체로 설정한다
• SingleLinkedList의 head가 존재하지 않다면 self.head에 item을 지정한다
• head가 이미 존재한다면 self.tail.next에 item을 입력한다

head는 단일 연결리스트의 첫 번째 노드가 무엇인가를 의미하는 정보, node는 아이템과 레퍼런스(data, next), item은 ListNode 클래스의 인스턴스로 값과 레퍼런스를 가지고 있다.

 

https://it-garden.tistory.com/318

단순연결리스트(Singly Linked List) 이론과 파이썬 구현

def add_list_item(self, item) : 
    if not isinstance(item, ListNode) : 
        item = ListNode(item) 

    if self.head is None : 
        self.head = item
    else : 
        self.tail.next = item 
        self.tail = item 
    return

 

3.2 list_length()

list_lenth() 메서드는 노드의 수와 리스트의 길이를 반환한다. 하나의 노드에서 다른 노드로 옮겨갈 때 self.next가 작동되며, 다음 노드를 위한 레퍼런스를 반환한다. 노드의 수를 세는건 다음 노드의 값이 None을 나타낼 때까지 while문을 반복하는 형식으로 만든다.

 

def list_length(self) : 
    count = 0
    current_node = self.head

    whlie current_node is not None : 
        count += 1 
        current_node = current_node.next

    return count

 

3.3 output_list()

output_list() 메서드는 노드의 값을 노드의 data 속성을 통해 출력한다.

 

def output_list(self) : 
    "output the list (the value of the node)"

    current_node = self.head

    while current_node is not None :
        print(current_node.data) 
        current_node = current_node.next 

    return

 

3.3 Usecase of ListNode

# create four single nodes
node1 = ListNode(15)
node2 = ListNode(8.2)
item3 = "Berlin"
node4 = ListNode(15)

# create Single-linked list 
track = SingleLinkedList()
print(f"track length : {track.list_length()}")

for current_item in [node1, node2, item3, node4] : 
    track.add_list_item(current_item) 
    track.output_list()

 

3.4 unorderd_search()

Single-linked list는 순차 검색으로 전체 데이터를 검사한다. 기존 list에서는 for loop의 index에 대해서 값을 이동했다면, single-linkied list는 각 node의 next를 통해 옆 노드로 넘어가게 된다.

 

def unorderd_search(self, values) : 
    current_node = self.head
    node_id = 1
    results = []
    
    while current_node is not None : 
        if current_node.has_value(value) : 
        	result.append(node_id) 
        current_node = current_node.next
        node_id += 1
        
    return results

 

4. ListNode Class

class ListNode: 
    def __init__(self, data = None) : 
        self.data = data
        self.next = None 
       
Class SlinkedList : 
    def __init__(self) : 
        self.head = None
        
    # Travsersing the linked list 
    def listprint(self) : 
        current_node = self.head
        while current_node is not None : 
            print(current_node.data) 
            current_node = current_node.next 
    
    # Insert item at beginning
    def insert_begin(self, newdata) :
        NewNode = ListNode(newdata) 
        NewNode.next = self.head
        self.head = NewNode 
    
    # Insert item at end 
    def insert_end(self, newdata) : 
        NewNode = ListNode(newdata) 
        if self.head is None : 
            self.head = NewNode
	    tail = self.head
        while tail.next is not None : 
        	tail = tail.next 
        tail.next = NewNode 
        
    def insert_between(self, middle_node, new_data) : 
        NewNode = ListNode(newdata) 
        NewNode.next = middle_node.next 
        middle_node.next = NewNode 
        
    # Remove an item 
    def RemoveNode(self, Removekey) : 
    	current_node = self.head
        
        if current_node is not None : 
        	if current_node.data == Removekey : 
            	self.head = current_node.next 
                current_node = None
                return
        while current_node is not None : 
            if current_node.data == Removekey : 
                break
            prev = current_node 
            current_node = current_node.next
            
       if current_node = None : 
           return 
           
       prev.next = current_node.next
       current_node = None

 

https://www.tutorialspoint.com/python_data_structure/python_linked_lists.htm

Python - Linked Lists

Python의 Single-linked list는 {value = , next : {value = , next : { ... }}} 형식으로 존재한다. 즉, 위의 ListNode 클래스 만으로 Sinlge-linked list를 정의 가능하며 밑에 있는 SListNode 클래스는 Single-linked list의 조작을 위한 메서드이다.