[Algorithm]SinglyLinked List by Python(연결 리스트)

colagom·2022년 5월 13일
0

Algorithm

목록 보기
2/2
post-thumbnail

Linked List란?

data element들이 메모리에서의 물리적 배치에 의해 순서가 정해지지 않고, 각 element들이 다음 element를 가리키며 만들어지는 자료구조이다.

이 element를 node라고 부르며 각 node는 값(val)과 다음 node의 주소(ref)를 갖는다.

Linked List의 성질

  1. k번째 element를 인덱싱하는 시간복잡도 O(k) <-> 배열은 O(1)
  2. 특정 위치의 element를 추가/제거하는 시간복잡도 O(1) <-> 배열은 O(N)

위의 그림에서 37을 인덱싱하는 경우 12의 ref로 99를 찾고 99의 ref로 37을 찾아야 하기 때문에 평균적으로 n/2의 시간이 걸리므로 시간복잡도는 O(N)이다.

만약 내가 99를 삭제하고 싶다면 다른 과정 없이 12번 node가 가진 다음 node의 ref를 37로만 고쳐주면 끝이다. 그렇기 때문에 시간복잡도는 O(1)이다.

우리가 List에 사용하는 익숙한 method들을 그대로 사용하기 위해 SinglyLinkedList를 구현해보면 다음과 같다.

class Node:  # Node 구현=> 데이터와 다음노드의 위치정보를 가지고있다.
    def __init__(self, data):
        self.data = data
        self.next = None


class SinglyLinkedList:
    def __init__(self):
        init = Node('init')
        self.head = init
        self.tail = init

        self.cur = None  # 현재 노드
        self.count = 0  # 전체 노드 개수

    def append(self, data):  # append method 생성
        curn = Node(data)  # 넣으려는 값을 node로 생성
        self.tail.next = curn  # 현재 tail의 다음값의 주소가 curn을 가리키게
        self.tail = curn  # 그리고 그 curn이 tail이 된다
        self.count += 1  # 노드의개수 +=1

    def __len__(self):  # len method 생성
        return self.count  # count값 return

    def __str__(self):  # <class 'str'>
        cur = self.head
        cur = cur.next  # init은 출력하지 않기 위해
        s = ''

        for i in range(self.count):  # 전체 노드를 순회하며 해당 값에 ', '를 추가하며 s에 더해준다.
            s += f'{cur.data}, '
            cur = cur.next

        return f'[{s[:-2]}]'  # s의 맨 끝이 ', ' 이기때문에 두 칸을 빼준다.

    def pop(self):  # 마지막노드 없애기
        lastNode = self.tail.data
        cur = self.head

        for i in range(self.count):
            if cur.next is self.tail:
                self.tail = cur
                break
            cur = cur.next

        self.count -= 1
        return lastNode

    def find(self, data):  # 해당 값의 index 출력
        index = -1
        cur = self.head

        for i in range(self.count):  # 노드의 개수만큼 반복문을 돌린다.
            if cur.data == data:  # 현재 노드의 값이 찾으려는값과 같으면 index반환
                return index
                break
            index += 1
            cur = cur.next

        return -1  # 만약 그 값이 없으면 -1 출력

    def __iter__(self):  # 순회
        cur = self.head
        cur = cur.next  # 이거 안하면 init부터나옴
        while cur:
            yield cur.data  # yield는 generator를 반환
            cur = cur.next

    def insert(self, input_index, input_data):  # 특정 인덱스에 데이터삽입
        cur = self.head

        for i in range(input_index):  # 해당 인덱스까지 이동
            cur = cur.next

        curn = Node(input_data)  # 새로운 노드 선언
        curn.next = cur.next
        cur.next = curn

        self.count += 1

method가 잘 적용되는지 실험해보면 다음과 같다.

l = SinglyLinkedList()
l.append(10)
l.append(20)
l.append(30)
l.append(40)

print(l.head.data)  # init
print(l.head.next.data)  # 10
print(l.head.next.next.data)  # 20
print(l.tail.data)  # 40
print(len(l))  # 4
for i in l:  # 10 20 30 40이 순서대로 출력된다. 만약 __iter__부분에서 cur=cur.next를 빼면 init 10 20 30 40  이런식으로 나온다.
    print(i)
l.insert(3, 1000000)
print(l)  # [10,20,30,1000000,40]

profile
Newbie Frontender

0개의 댓글