Data Structure - Linked List(연결리스트)

1.. Linked List 란?

• 원소를 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조

• Linked List는 Node라는 객체로 구성

  • 데이터를 저장할 수 있는 필드인 Data or Key
  • 다음 Node를 가르키는 Next 포인터로 구성

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

예를 들어, 학교에 영은, 현지, 재현, 상혁이라는 4명에 학생이 있다고 가정하면 배열(Array)에서는 그냥 4칸짜리 배열을 만들고 4명을 저장하면 되지만, 연결리스트의 관점에서는 영은 ➤ 현지 ➤ 재현 ➤ 상혁의 식으로 다음 사람만 기억하면 된다. 이렇게되면 영은이만 외워두면 영은이를 통해서 나머지 3명이 누구인지 알아낼 수 있다.

2.. Linked List의 성질

1. n 번째 원소를 확인 or 변경 = O(n)
2. 임의의 위치에 원소를 추가 or 제거 = O(1)
3. 원소들이 메모리 상에 연속해있지 않기 때문에 Cache hit rate이 낮지만, 할당이 다소 쉬움

3.. Linked List의 종류

• 단일 연결 리스트(Signly Linked List)
  : 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트
  

• 이중 연결 리스트(Doubly Linked List)
  : 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 들고 있는 연결 리스트
  : 주어진 원소의 이전 원소가 무엇인지 알 수 있음
  : 다만, 원소가 가지고 있어야 하는 정보가 1개 더 추가되어 메모리를 더 쓴다는 단점이 있음
  

• 원형 연결 리스트(Circular Linked List)
  : 끝이 처음과 연결되어 있는 연결 리스트
  

4.. Linked List 구현

class Node:
	def __init__(self, key=None):
    	self.key = key
        self.next = None # "link"를 next로 표현
    
    def __str__(self):
    	return str(self.key)
        # 나중에 키 값을 출력되게끔 동작하게 하기위해 스트링 함수를 method로 선언

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


# LinkedList 클래스 (자료구조) 정의
class LinkedList:

    # 초기화 메소드
    def __init__(self):
        dummy = Node("dummy")
        self.head = dummy
        self.tail = dummy

        self.current = None
        self.before = None

        self.num_of_data = 0

    # append 메소드 (insert - 맨 뒤에 노드 추가, tail과 node의 next, 데이터 개수 변경)
    def append(self, data):
        new_node = Node(data)
        self.tail.next = new_node
        self.tail = new_node

        self.num_of_data += 1

    # delete 메소드 (delete - current 노드 삭제, 인접 노드의 current, next 변경, 데이터 개수 변경)
    def delete(self):
        pop_data = self.current.data

        if self.current is self.tail:
            self.tail = self.before

        self.before.next = self.current.next
        self.current = self.before # 중요 : current가 next가 아닌 before로 변경된다.
        #

        self.num_of_data -= 1

        return pop_data

    # first 메소드 (search1 - 맨 앞의 노드 검색, before, current 변경)
    def first(self):
        if self.num_of_data == 0: # 데이터가 없는 경우 첫번째 노드도 없기 때문에 None 리턴
            return None

        self.before = self.head
        self.current = self.head.next

        return self.current.data

    # next 메소드 (search2 - current 노드의 다음 노드 검색, 이전에 first 메소드가 한번은 실행되어야 함)
    def next(self):
        if self.current.next == None:
            return None

        self.before = self.current
        self.current = self.current.next

        return self.current.data

    def size(self):
        return self.num_of_data