파이썬으로 Linked List 만들기

 

연결되는 방향에 따라 singly linked list, doubly linked list, circular linked list가 있다.

CS에서 배열과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나로 다양한 추상 자료형(ADT)구현의 기반이 된다.

동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하다. 그래서 동적인 메모리 할당으로 메모리 관리에 용이하다.

연결구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리가 쉽다. 또한 데이터를 구조체로 묶어서 포인터로 연결한다는 개념은 여러가지 방법으로 다양하게 활용이 가능하다.

데이터를 노드의 형태로 저장

노드에는 데이터와 다음 노드를 가리키는 포인터를 담은 구조로 이루어져 있다.

 

출처:https://www.geeksforgeeks.org/data-structures/linked-list/

 

연결리스트는 데이터 요소의 선형집합으로, 데이터의 순서가 메모리에 물리적인 순서대로 저장되지는 않는다. 실제 컴퓨터의 물리메모리에는 구조체 각각이 서로 연결된 형태로 구성되어 있으며, 메모리 어딘가 여기저기 흩뿌려진 형상을 띤다.

연결리스트는 배열과 다르게 특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 하므로 상수시간에 접근할 수 없다. 즉 탐색에는 최대 O(n)이 소요된다. (탐색할 때, 첫 노드부터 탐색을 시작해야 하므로 배열보다는 상대적으로 느림)( 사실상 삽입과 삭제가 왼쪽에서(Head에서) 이루어지지 않을 경우, 결국 탐색을 먼저 해야 하기 때문에 삽입과 삭제 모두 적게는 O(k)부터 최악의 경우 O(N)까지 걸릴 가능성이 있다.) 반면 시작 또는 끝지점에 아이템을 추가하거나 삭제, 추출하는 작업은 O(1)에 가능하다.

파이썬에서는 리스트로 연결리스트를 구현한다.

장점: Linked List의 길이를 동적으로 저절 가능/ 데이터의 삽입과 삭제가 쉬움.

단점: 임의의 노드에 바로 접근 불가./ 다음 노드의 위치를 저장하기 위한 추가공간이 필요함/ 연결리스트를 거꾸로 탐색하기 어려움

 

파이썬으로 singly linked list 만들기

 

# Single Linked List
 
class Node(object): #node class
    def __init__(self, data, next=None): #생성자
        self.data = data
        self.next = next
 
 
class SList(object): #연결리스트
    def __init__(self):
        self.head = Node(None) #첫 연결리스트 생성시 data=None, next=None인 node가 한개인 연결리스트가 생성됨
        self.size = 0
 
    def listSize(self):
        return self.size
 
    def is_empty(self): #연결리스트가 비어있나 없나 확인
        if self.size != 0:
            return False
        else:
            return True
    #1
    def selectNode(self, idx): #해당 노드 조회
        if idx >= self.size:
            print("Index Error")
            return None
        if idx == 0:
            return self.head
        else:
            target = self.head #head부터 탐색
            for cnt in range(idx): #idx
                target = target.next
            return target
    #2
    def appendleft(self, value):
        if self.is_empty(): #linked list is empty
            self.head = Node(value)
        else:
            self.head = Node(value, self.head) #head에 new node make
        self.size += 1
    #3
    def append(self, value): #end 부분에 new node make
        if self.is_empty(): #empty
            self.head = Node(value)
            self.size += 1
        else:
            target = self.head
            while target.next != None: #end노드가 아닐 동안
                target = target.next #계속 end를 향해 move
            newtail = Node(value) #new node 생성
            target.next = newtail #end 노드에 new node연결
            self.size += 1
    #4
    def insert(self, value, idx):  #연결리스트의 중간에 새로운 노드를 insert
        # =>삽입할 자리의 앞의 노드의 next부분이 새로운 노드를 가리키게 해야하고, 새로운 노드는 이전노드가 가리키던 다음노드를 next로 가리키게 해아한다.
        if self.is_empty():
            self.head = Node(value)
            self.size += 1
        elif idx == 0: #첫 노드에 새로운 노드를 insert
            self.head = Node(value, self.head)  #old head를 new node의 next포인터가 가리키게 하고 new node 생성
            self.size += 1
        else: #중간에 노르를 insert
            target = self.selectNode(idx - 1) #first, 조회먼저^^ target은 이전노드
            if target == None:
                return
            newNode = Node(value)
            tmp = target.next
            target.next = newNode #이전노드가 new node를 가리키게 (이전노드와 다음노드의 연결고리를 끊음)
            newNode.next = tmp #new node가 다음노드를 가리키게
            self.size += 1
    #5
    def delete(self, idx):
        if self.is_empty():
            print('Underflow: Empty Linked List Error')
            return
        elif idx >= self.size:
            print('Overflow: Index Error')
            return
        elif idx == 0:
            target = self.head #target은 head노드
            self.head = target.next #head의 다음노드가 head가 된다.
            del (target) #delete
            self.size -= 1 #size--
        else:
            target = self.selectNode(idx - 1) #target은 해당 idx의 바로 전 노드
            deltarget = target.next
            target.next = target.next.next #idx의 바로 전노드와 삭제할 노드의 연결고리 끊기, target이 삭제할 노드가 가리키던 노드를 가리키게 함
            del (deltarget)
            self.size -= 1
 
    def printlist(self): #연결리스트 출력
        target = self.head
        while target:
            if target.next != None:
                print(target.data, '-> ', end='')
                target = target.next
            else:
                print(target.data)
                target = target.next

이게 기본 코드이다.

 

 

 

 

 

 

 

 

[내용 출처]www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9791189909178

[내용 출처]daimhada.tistory.com/72

[소스코드 출처]underflow101.tistory.com/3