단일 연결리스트 - Singly Linked List

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

정의

어떤 데이터 덩어리(Node)를 저장할 때 그 다음 좌표가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장하는 구조이다.

배열과 비교

• 장점 - 새로운 노드를 뒤에 연결하거나 중간에 노드를 끼워넣기가 쉽다. 즉, 크기를 키우거나 줄이기가 쉽다.

• 단점 - 자료번호로 데이터를 구분하는 배열과 달리 연결관계만 가지고 있기 때문에 특정 노드를 불러오기가 힘들다.

• 결론 - 탐색/정렬은 배열이, 추가/ 삭제는 연결리스트가 유리하다. 물론 순차 탐색만 하지 않고 효율적인 탐색을 한다면 단점이 없어진다. 그에 관한 내용은 추가적으로 공부하면 작성할 예정.

  Python의 리스트가 너무 사기적으로 슬라이싱, 동적 할당을 지원하기에 실제 문제에서 적용하기 조금 애매한 경우도 있다.

시간복잡도

유형

1. 단일 연결리스트(Singly Linked List)

   다음 노드에 대한 참조값만을 갖는 가장 단순한 형태의 연결리스트다. 큐를 구현할 때 사용하는 방식이다. 단방향이기 때문에 역방향 탐색이 어려운 단점이 있다. 알고리즘 문제에서 역방향 탐색을 요구하지 않는 문제가 나오면 단일 연결리스트를 구현해서 풀기도 한다.

2. 이중 연결리스트(Doubly Linked List)

   단일 연결리스트가 다음 노드에 대한 참조값만을 가졌다면 이중 연결리스트는 이전 노드에 대한 참조값도 갖는다.

3. 환(원)형 연결리스트(Circular Linked List)

   단일 연결리스트에서 마지막 노드의 참조값은 Null이지만 이를 첫 번째 노드를 가리키게 하면 환형 연결리스트가 된다. 이중 연결리스트의 경우에도 처음 노드의 이전 노드 참조값을 마지막 노드로, 마지막 노드의 다음 노드 참조값을 첫 번째 노드로 가리키게 하면 된다.

단일 연결리스트(Singly Linked List) 구현

Node 정의

class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

Singly Linked List 정의

class SinglyLinkedList(object):
    def __init__(self):
        self.head = ListNode(None)
        self.size = 0

Singly Linked List 사이즈 반환

    def size(self):
        return self.size

Singly Linked List 원소 조회

    def get_node(self, idx):
        if self.size == 0: # 빈 연결리스트 에러 출력
            print("ERROR: Already Empty Linked List")
            return
        elif idx >= self.size: # 연결리스트보다 큰 입력이라면
            print("ERROR: Out of Range") # 에러 출력
            return
        else:
            target = self.head # 0번 노드 지정
            for _ in range(idx): # idx 좌표까지 진행
                target = target.next
            return target # idx 좌표 노드 반환

Singly Linked List 원소 우측 삽입

    def append(self, val):
        if self.size == 0: # 빈 연결리스트면
            self.head = ListNode(val) # 0번 좌표 입력
        else: # 이미 존재하면 get_node로 마지막 좌표 조회
            target = self.get_node(self.size - 1)
            target.next = ListNode(val) # 다음 노드 생성
        self.size += 1 # 사이즈 갱신

Singly Linked List 원소 좌측 삽입

    def appendleft(self, val):
        if self.size == 0: # 빈 연결리스트면 0번 좌표 생성
            self.head = ListNode(val)
        else: # 그게 아니면 head 생성 및 기존 head를 next로
            self.head = ListNode(val, self.head)
        self.size += 1 # 사이즈 갱신

Singly Linked List 좌표 기반 원소 삽입

    def insert(self, val, idx):
        if self.size == 0: # 이미 비었다면 에러 출력
            print("ERROR: Already Empty Linked List")
        elif idx >= self.size: # idx 범위 오류 시 에러 출력
            print("ERROR: Out of Range")
        else:
            target = self.get_node(idx - 1) # 그외 idx-1번 좌표 조회
            tmp = target.next # 기존 idx번 노드 임시 저장
            target.next = ListNode(val, tmp) # 노드 생성
            self.size += 1 # 기존 노드 뒤로 미루고 사이즈 갱신

Singly Linked List 원소 우측 삭제

    def pop(self):
        if self.size == 0: # 이미 빈 리스트면 에러 출력
            print("ERROR: Already Empty Linked List")
        else:
            target = self.get_node(idx - 2) # 마지막 2번 노드 조회
            out = target.next # 마지막 노드 조회
            target.next = None # 마지막 2번 노드의 다음 노드 제거
            self.size -= 1 # 사이즈 갱신
            return out # 기존 마지막 노드 반환

Singly Linked List 좌표 기반 원소 삭제

    def delete(self, idx):
        if self.size == 0: # 이미 비었다면 에러 출력
            print("ERROR: Already Empty Linked List")
        elif idx >= self.size: # idx 범위 오류 시 에러 출력
            print("ERROR: Out of Range")
        else:
            target = self.get_node(idx - 1) # idx-1번 노드 조회
            target.next = target.next.next # idx번 노드 덮어씌움

Singly Linked List 원소 출력

    def print(self):
        target = self.head # 0번 원소 조회
        while target: # None이 올 때까지
            if target.next != None: # 다음 노드 존재하면 아래 출력
                print(f'{target.val} -> ', end='')
            else: # 다음 노드가 없다면(마지막 노드)
                print(target.val) # 값만 출력
            target = target.next # 다음 노드 진행

실습 결과

linked_list = SingleLinkedList()
linked_list.append(1)
linked_list.print()
linked_list.append(2)
linked_list.print()
linked_list.appendleft(0)
linked_list.print()
linked_list.append(4)
linked_list.insert(3, 3)
linked_list.print()
linked_list.delete(0)
linked_list.print()
a = linked_list.pop()
print(f'a value is {a.val}')
linked_list.print()
b = linked_list.popleft()
print(f'b value is {b.val}')
linked_list.print()