[자료구조/알고리즘] Single Linked List (단일 연결 리스트)

단일 연결 리스트 자료구조

연결 리스트는 실행 시간에 메모리를 할당하거나 해제할 수 있는 동적 자료구조이다.

이번 포스팅에서는 단일 연결 리스트의 개념과 단일 연결 리스트 연산들의 구현에 대해 간단하게 정리해 보았다. 참고로 사용한 언어는 python이다.

1. 연결 리스트의 개념

• 연결 리스트 자료구조는 배열처럼 선형 자료구조에 속하지만 인덱스로 접근하는 것이 아닌, 각 노드가 다음 노드에 대한 참조를 갖는 구조이다. 배열처럼 자료들의 메모리가 선형적으로 저장되지 않고 흩어져(?) 있지만 각 노드의 참조를 갖고 있기 때문에, 그 참조를 따라 다음 노드로 접근할 수 있다. 아래의 그림을 보면 쉽게 이해할 수 있다.

  

• 각 노드는 데이터를 담는 data field와 다음 노드를 참조하는 pointer field를 갖고 있다. 첫 번째 노드는 head 노드라고 하며, 마지막 노드를 tail 노드라고 한다. 아래의 코드는 단일 연결 리스트의 노드를 정의하는 함수이다. 속성으로 데이터를 넣는 data와 다음 노드를 가리키는 pointer인 next 속성을 갖는다. node에 저장할 데이터를 인수로 받고 저장한다.

class Node:
    """링크드 리스트의 노드 클래스"""

    def __init__(self, data):
        self.data = data  # 실제 노드가 저장하는 데이터
        self.next = None  # 다음 노드에 대한 레퍼런스

• 다음 코드는 노드를 연결해주는 단일 연결 리스트를 정의하는 코드이다. head는 연결 리스트의 첫 번재 노드를 참조한다.

class LinkedList:
    """링크드 리스트 클래스"""

    def __init__(self):
        self.head = None
        self.tail = None

2. 연결리스트의 연산들

연결리스트의 기본적인 연산으로는 삽입, 삭제, 검색 이 있다. 순서대로 구현에 대해 알아보자

1. 삽입

삽입 연산은 세 경우로 나뉜다.

1) 링크드 리스트의 맨 뒤에 노드를 추가하는 연산

맨 뒤에 추가하는 연산은 append라고 하며, 아래 두 경우로 나뉠 수 있다.

링크드 리스트가 비어있는 경우 : 새로 넣는 node가 head 노드이자 tail 노드가 된다. head와 tail이 같이 new node를 가리키도록 한다.

링크드 리스트가 비어있지 않은 경우 : 가장 마지막 node 뒤에 새로운 node를 추가한다.

def append(self, data):
        """링크드 리스트 추가 연산 메소드"""
        new_node = Node(data)

        # 링크드 리스트가 비어 있으면 새로운 노드가 링크드 리스트의 처음이자 마지막 노드다
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        # 링크드 리스트가 비어있지 않으면
        else:
            self.tail.next = new_node  # 가장 마지막 노드 뒤에 새로운 노드를 추가하고
            self.tail = new_node  # 마지막 노드를 추가한 노드로 바꿔준다.

2) 링크드 리스트의 노드 사이에 노드를 추가하는 연산

인자로 이전 노드와 넣을 데이터를 받고 이전 노드의 다음 노드로 새로운 노드를 추가한다.

인자로 받은 노드의 다음 노드로 추가를 하기 때문에 메서드의 이름은 insert_after이다

insert_after도 다음 두 경우로 나눈다.

• 가장 마지막 순서에 삽입할 경우

이 경우는 인자로 받은 node가 가장 마지막에 있는 tail인 경우이다.

append와 비슷하다.

• 두 노드 사이에 삽입할 경우 이전 노드가 가리키는 reference를 새로운 노드를 가리키게 하고, 새로운 노드의 reference를 이전 노드가 가리키던 다음 노드를 가리키게 한다.

  

def insert_after(self, previous_node, data):
        """링크드 리스트 주어진 노드 뒤 삽입 얀신 메소드"""
        #! 이 방법은 head node 앞에는 새로운 노드를 추가할 수 없다는 단점이 있다. (가장 앞에 삽입 불가)
        new_node = Node(data)

        # 노드의 삽입은 가장 마지막에 삽입할 경우와 노드 사이에 삽입할 경우로 나뉜다.
        # 가장 마지막 순서에 삽입할 때: tail 노드 다음에 노드를 삽입할 때
        if previous_node is self.tail:
            self.tail.next = new_node
            self.tail = new_node
        # 두 노드 사이에 삽입할 때 : 두 노드 사이에 새로운 노드를 삽입할 때
        else:
            new_node.next = previous_node.next
            previous_node.next = new_node

3) 링크드 리스트의 맨 앞에 노드를 추가하는 연산

위에서 구현한 insert_after는 이전 노드를 매개변수로 받고 그 앞에 추가하기 때문에 맨 앞의 node에 추가하지 못하기 때문에 맨 앞에 노드를 추가하는 메서드가 따로 필요하다. 맨 앞에 추가하는 메서드이므로 prepend라고 명칭 한다.

prepend는 append와 같이 링크드 리스트에 아무 노드도 없는 경우와 있는 경우로 나뉜다.

• 링크드 리스트가 비어있는 경우 : 새로 넣는 node가 head 노드이자 tail 노드가 된다. head와 tail이 같이 new node를 가리키도록 한다.

  

• 링크드 리스트가 비어있지 않은 경우 : 새로운 노드의 next가 현재 head가 가리키는 노드를 가리키게 하고 , head는 새로 추가되는 node를 가리키게 한다.

  

def prepend(self, data):
        """링크드 리스트의 가장 앞에 데이터 삽입"""
        # 코드를 쓰세요
        new_node = Node(data)  # 추가 할 새로운 노드를 생성한다
        # head node가 비어있다면
        if self.head is None:
            self.head = new_node  # head에 새로운 노드를 할당한다.
            self.tail = new_node  # tail에 새로운 노드를 항당한다.
        # 비어있지 않다면
        else:
            # 새로운 노드의 next가 현재 head가 가리키는 노드를 가리키게 한다.
            new_node.next = self.head
            self.head = new_node  # head가 새로운 노드를 가리키게 한다..

2. 삭제

삭제 연산은 주어진 노드의 앞의 노드를 삭제하는 메서드와 head에 있는 노드를 삭제하는 메서드로 나뉜다.

delete_after는 주어진 노드의 앞에 있는 노드를 삭제하는 함수이다.

1) 주어진 인자의 앞의 노드를 삭제하는 함수

삭제하려는 노드가 tail인 경우와 아닌 경우로 나뉜다.

• 삭제하려는 노드가 tail인 경우

인자로 받은 이전 노드(previous_node)가 가리키는 reference를 끊고 tail이 이전 노드를 가리키게 한다.

• 삭제하려는 노드가 누 노드 사이일 경우

인자로 받은 이전 노드의 reference가 다음, 다음의 노드를 가리키게 한다.

def delete_after(self, previous_node):
        """링크드 리스트 삭제 연산. 주어진 노드 뒤 노드를 삭제한다"""
        data = previous_node.next.data
        # 지우려는 노드가 tail 노드 일 때:
        if previous_node.next is self.tail:
            previous_node.next = None  # previous_node가 가리키는 노드를 None으로 처리한다.
            self.tail = previous_node
        # 두 노드 사이 노드를 지울 때
        else:
            previous_node.next = previous_node.next.next
        return data

2) 맨 앞의 노드를 삭제하는 경우

위의 delete_after는 인자로 받은 이전 노드의 다음 노드를 삭제하는 기능만 가능하다. 그러므로 head 노드를 삭제하는 메서드가 추가로 필요하다.

이 메서드는 링크드 리스트에 1개의 노드만 존재하여 삭제할 경우 아무 노드도 없어질 경우와 아닌 경우로 나뉜다.

1개의 노드만 남았다면 head와 tail이 None을 가리키게 하고 아니라면 head가 head의 next를 가리키게 한다.

def pop_left(self):
        """링크드 리스트의 head노드를 삭제"""
        data=self.head.data
        # 만약 링크드 리스트에 1개의 노드만 존재할 경우
        if self.head.next is None:
            self.head=None # head가 None을 가리키게 한다
            self.tail=None # tail이 None을 가리키게 한다
        # 아니라면 
        else:
            self.head=self.head.next # 현재 head가 가리키고있는 node를 현재 노드의 다음 노드를 가리키게 한다.
        return data

3. 접근 & 탐색

링크드 리스트의 접근과 탐색은 head부터 작하여 순차적으로 진행된단.

1) 링크드 리스트 접근 - 해당 인덱스에 접근하여 node 찾기

head 부터 시작하여 해당 index에 있는 node까지 접근 후 return 한다.

def find_node_at(self, index):
        """링크드 리스트 접근 연산 메소드. 파라미터 인덱스는 항상 있다고 가정한다."""

        iterator = self.head  # 링크드 리스트를 돌기 위해 필요한 노드 변수

        # index 번째 있는 노드로 간다.
        for _ in range(index):
            iterator = iterator.next

        return iterator

2) 링크드 리스트 탐색 - 데이터에 해당하는 node 찾기

daat를 인자로 받고 head 노드부터 시작하여 data를 비교하면서 해당되는 node를 찾는다.

def find_node_with_data(self, data):
        """링크드 리스트에서 탐색 연산 메소드. 단, 해당 노드가 없으면 None을 리턴한다"""

        iterator = self.head
        while iterator is not None:
            if iterator.data == data:
                return iterator
            iterator = iterator.next
        return None

3. Linked List의 시간 복잡도

Linked List 연산들의 시간 복잡도

연산	시간 복잡도
접근	O(n)
탐색	O(n)
삽입	O(n+1)
삭제	O(n+1)

접근

접근을 하기 위해서는 head 노드부터 x번 다음 노드를 찾아가야 한다. 노드의 수가 n이라고 하면 마지막 순서에 있는 노드에 접근하는 "최악"의 경우에는 head 노드에서부터 n-1번 다음 노드로 가야 한다. 걸리는 시간은 n에 비례하게 되므로 최악의 경우 O(n)의 시간 복잡도를 갖게 된다.

탐색

링크드 리스트에서의 탐색을 배열과 같이 순차적으로 하는 선형 탐색을 한다. 이 경우에도 최악의 경우 찾으려는 데이터가 마지막에 있을 경우 n개의 노드를 다 봐야 하므로 O(n)의 시간 복잡도를 갖는다.

삽입/삭제

삽입, 삭제의 경우 삽입 또는 삭제할 인덱스의 주변 노드들에 연결된 레퍼런스만 수정하므로 특정 값에 비례하지 않고 항상 일정하므로 O(1)의 시간 복잡도를 갖는다.

현식적인 삽입/삭제 시간 복잡도

삽입, 삭제 연산을 진행하기 전에 먼저 이들의 인자로 넘겨주어야 할 노드를 찾아야 한다. head와 tail은 항상 저장이 되어있기 때문에 빨리 찾을 수 있지만 나머지 노드들은 탐색 또는 접근 연산을 통해 찾아야 한다.

따라서, 현실적인 시간 복잡도는 다음과 같다.

<  현실적인 시간 복잡도  >

연산	링크드 리스트
접근	O(n)
탐색	O(n)
원하는 노드에 접근 또는 탐색 + 삽입	O(n+1)
원하는 노드에 접근 또는 탐색 + 삭제	O(n+1)

 

삽입/삭제 연산 특수 경우 시간 복잡도

• tail과 head로 연산을 진행하는 경우는 O(1)의 시간 복잡도를 갖는다.
  • tail 노드를 삭제하는 경우엔 전 노드가 필요하며, 이 노드를 탐색하기 위해 head 노드에서 n-2번의 연산이 필요하다. —> O(n)의 시간 복잡도가 추가된다.
  head, tail을 통한 연산을 하는 경우의 시간 복잡도
  
  
  

  연산	링크드 리스트
  가장 앞에 접근 + 삽입	O(1+1)
  가장 앞에 접근 + 삭제	O(1+1)
  가장 뒤에 접근 + 삽입	O(1+1)
  뒤에서 두 번째 노드(tail 노드 전 노드) 접근 삭제	O(n+1)

  다음 포스팅은 이중 연결 리스트의 개념과 구현 방법, 시간 복잡도에 대해 포스팅을 하겠다.