Notice

Recent Posts

Recent Comments

Link

« 2025/05 »
일	월	화	수	목	금	토
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Tags more

Archives

Today

Total

관리 메뉴

새로새록

자료구조 - 링크드 리스트 연산들 본문

소프트웨어융합/코드잇 정리.py

자료구조 - 링크드 리스트 연산들

류지나 2022. 2. 3. 21:49

접근

인덱스 x에 있는 데이터에 접근하려면 링크드 리스트의 head 노드부터 x 번 다음 노드를 찾아서 가야 됩니다. 원하는 노드에 접근하는 시간은 몇 번째 인덱스인지에 비례하는 건데요. 그러니까 인덱스 1에 있는 노드는 head 노드에서 한 번만 다음 노드로 가면 되고 인덱스 5에 있는 노드는 head 노드에서 연속해서 5 번 이동하면 되는 거죠.

링크드 리스트 안에 있는 노드의 수를 이라고 하면, 마지막 순서에 있는 노드에 접근해야 되는 최악의 경우에는 head 노드에서 총 n - 1 번 다음 노드로 가야 됩니다. 걸리는 시간은 에 비례하기 때문에 접근 연산은 최악의 경우 O(n의 시간 복잡도를 갖습니다.

탐색

링크드 리스트 탐색 연산은 배열을 탐색할 때와 같은 방법으로 합니다. 가장 앞 노드부터 다음 노드를 하나씩 보면서 원하는 데이터를 갖는 찾습니다. 이런 탐색 방법을 선형 탐색이라고 했는데요. 접근과 마찬가지로 링크드 리스트 안에 찾는 데이터가 없을 때 또는 찾으려는 데이터가 마지막 노드에 있는 최악의 경우, n 개의 노드를 모두 다 봐야 됩니다. 그렇기 때문에 탐색도 접근과 마찬가지로 최악의 경우 O(n)의 시간 복잡도를 갖습니다.

삽입/삭제

링크드 리스트의 삽입과 삭제 연산은 배열 삽입과 조금 차이가 있었는데요. insert_after, delete_after 메소드들을 한 번 살펴보세요.

def insert_after(self, previous_node, data):
    """파라미터 data를 데이터로 갖는 새로운 노드를 만들어서 node 파라미터 뒤에 삽입시킨"""
    new_node = Node(data) # 새로운 노드 만들기

    # tail 노드 다음에 새로운 노드를 삽입할 때
    if previous_node == self.tail: 
        previous_node.next = new_node
        self.tail = new_node
    # 두 노드 사이에 새로운 노드를 삽입할 때
    else:
        new_node.next = previous_node.next
        previous_node.next = new_node

def delete_after(self, previous_node):
    """파라미터로 받은 노드 다음 노드를 삭제한다. 단, 파라미터 previous노드로 인해서 에러는 안 난다고 가정한다"""
    data = previous_node.next.data

    # 지우려는 노드가 tail 노드일 때
    if previous_node.next == self.tail:
        self.tail = previous_node
        self.tail.next = None
    # 두 노드 사이의 노드를 지울 
    else:
        previous_node.next = previous_node.next.next

    return data

삽입, 삭제는 그냥 삽입, 삭제할 인덱스의 주변 노드들에 연결된 레퍼런스만 수정합니다

그러니까 이 연산들이 실행되는데 걸리는 시간은 특정 값에 비례하지 않고 항상 일정하다는 말인데요. 의 시간 복잡도를 갖는다고 할 수 있습니다.

시간 복잡도

모든 걸 종합해보면 이렇게 나타낼 수 있습니다.

연산시간 복잡도

접근	O(n)
탐색	O(n)
삽입	O(1)
삭제	O(1)

접근과 탐색은 O(n), 삽입과 삭제는 O(1)이죠.

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

삽입과 삭제 연산들은 특정 노드를 넘겨줘서 이 노드 다음 순서에 데이터를 삽입하거나 삭제했잖아요? 그럼 이 연산들에 넘겨주는 노드, 파라미터 previous_node를 먼저 찾아야 되는데요. head와 tail 노드는 항상 저장해주기 때문에 빨리 찾을 수 있는데, 나머지 노드들은 탐색이나 접근 연산을 통해서 가지고 와야 됩니다.

연산링크드 리스트

접근	O(n)
탐색	O(n)
원하는 노드에 접근 또는 탐색 + 삽입	O(n + 1)
원하는 노드에 접근 또는 탐색 + 삭제	O(n + 1)

사실상 삽입과 삭제 연산은 접근 또는 탐색의 시간 복잡도인 O(n)를 공유한다고 볼 수 있습니다.

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

근데 아까 얘기했듯이, head와 tail 노드는 항상 한 번에 찾을 수 있었죠?

접근하는데 O(1), 연산을 하는데 O(1)이 걸리는데요. 그렇기 때문에 이 두 노드와 관련. 있는 삽입이나 삭제 연산들은 O(1)로 할 수 있습니다. append, prepend, pop_left 메소드를 살펴보면 head 노드와 tail 노드를 한 번에 가지고 와서 레퍼런스를 바꿔주죠?

def pop_left(self):
    """링크드 리스트의 가장 앞 노드를 삭제해주는 메소드, 단 링크드 리스트에 항상 노드가 있다고 가정한다"""
    data = self.head.data  # 삭제할 노드를 미리 저장해놓는다

    # 지우려는 데이터가 링크드 리스트의 마지막 남 데이터일 때
    if self.head is self.tail:
        self.head = None
        self.tail = None
    else:
        self.head = self.head.next

    return data  # 삭제된 노드의 데이터를 리턴한다


def prepend(self, data):
    """링크드 리스트의 가장 앞에 데이터 삽입"""
    new_node = Node(data)  # 새로운 노드를 만든다

    # 링크드 리스트가 비었는지 확인
    if self.head is None:
        self.tail = new_node
    else:
        new_node.next = self.head   # 새로운 노드의 다음 노드를 head 노드로 정해주고

    self.head = new_node   # 리스트의 head_node를 새롭게 삽입한 노드로 정해준다


def append(self, data):
    """파라미터로 받은 데이터를 갖는 노드를 생성한다"""
    new_node = Node(data)

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

링크드 리스트 안에 몇 개의 노드가 있던 상관없이, 항상 한 번에 받아와서 레퍼런스를 바꿔줍니다.

연산링크드 리스트

가장 앞에 접근 + 삽입	O(1 + 1)
가장 앞에 접근 + 삭제	O(1 + 1)
가장 뒤에 접근 + 삽입	O(1 + 1)

양 끝에서 하는 삽입/삭제 연산들 중 유일하게 tail 노드를 삭제하는 경우는 빠졌죠?

tail 노드를 삭제하기 위해서는 바로 전 노드가 필요한데요. 이 노드를 찾으려면 head 노드에서 n - 2번 다음 노드로 가야 됩니다. 접근하는데 O(n - 2, 그러니까 O(n)의 시간 복잡도가 걸립니다. 접근한 노드에서 다음 노드를 삭제하는 건 O(1)이 걸리잖아요?. 그러니까 tail 노드 전 노드에 접근해서 tail 노드를 삭제하는 건 O(n + 1, 결국 O(n)인 거죠.

연산링크드 리스트

가장 앞에 접근 + 삽입	O(1 + 1)
가장 앞에 접근 + 삭제	O(1 + 1)
가장 뒤에 접근 + 삽입	O(1 + 1)
뒤에서 두 번째 노드 (tail 노드 전 노드) 접근 + 삭제	O(n + 1)

링크드 리스트 가장 뒤 노드 삭제 연산은 나머지 세 연산만큼 효율적으로 할 수 없습니다.

head_node = Node(2)
node_1 = Node(3)
node_2 = Node(5)
node_3 = Node(7)
tail_node = Node(11)

head_node.next = node_1
node_1.next = node_2
node_2.next = node_3
node_3.next = tail_node
iterator = head_node

while iterator is not None:
print(iterator.data)
iterator = iterator.next

class Node:
    """링크드 리스트의 노드클래스"""
    def __init__(self, data):
        self.data = data
        self.next = None
        
class LinkedList:
    """링크드 리스트 클래스"""
    def __init__(self):
        self.head =None
        self.tail =None
    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

링크드 리스트 str 메소드

class LinkedList:
    """링크드  리스트 클래스"""
    def __init__(self):
        self.head = None  # 링크드 리스트의 가장 앞 노드
        self.tail = None  # 링크드 리스트의 가장 뒤 노드

    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  # 마지막 노드를 추가한 노드로 바꿔준다

    def __str__(self):
        """링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
        res_str = "|"

        # 링크드  리스트 안에 모든 노드를 돌기 위한 변수. 일단 가장 앞 노드로 정의한다.
        iterator = self.head

        # 링크드  리스트 끝까지 돈다
        while iterator is not None:
            # 각 노드의 데이터를 리턴하는 문자열에 더해준다
            res_str += f" {iterator.data} |"
            iterator = iterator.next  # 다음 노드로 넘어간다

        return res_str

__str__ 메소드는 문자열을 리턴하니까 일단 리턴 시킬 res_str 변수를 빈 문자열로 정의합니다. iterator을 써서 링크드 리스트를 도는 방법은 이미 배웠죠?

iterator 변수를 링크드 리스트의 head를 가리키게 합니다
iterator 변수가 None이 아닐 때까지 (링크드 리스트의 처음부터 끝 노드까지) iterator 변수의 data를 res_str 변수에 추가해 줍니다. iterator 변수의 next 속성을 이용해서 while 문을 돌 때마다 다음 노드로 갑니다.
링크드 리스트를 다 돈 후에 res_str 변수를 리턴합니다.

링크드 리스트 탐색 연산

class Node:
    """링크드 리스트의 노드 클래스"""
    def __init__(self, data):
        self.data = data  # 실제 노드가 저장하는 데이터
        self.next = None  # 다음 노드에 대한 레퍼런스

class LinkedList:
    """링크드 리스트 클래스"""
    def __init__(self):
        self.head = None  # 링크드 리스트의 가장 앞 노드
        self.tail = None  # 링크드 리스트의 가장 뒤 노드

    def find_node_with_data(self, data):
        """링크드 리스트에서 탐색 연산 메소드. 단, 해당 노드가 없으면 None을 리턴한다"""
        iterator = self.head  # 링크드 리스트를 돌기 위해 필요한 노드 변수
    
        # 링크드 리스트 전체를 돈다
        while iterator is not None:
            # iterator 노드의 데이터가 찾는 데이터면 iterator를 리턴한다
            if iterator.data == data:
                return iterator
            iterator = iterator.next  # 다음 노드로 넘어간다
    
        # 링크드 리스트 안에 원하는 데이터가 없었기 때문에 None 리턴한다
        return None 

    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  # 마지막 노드를 추가한 노드로 바꿔준다

    def __str__(self):
        """링크드  리스트를 문자열로 표현해서 리턴하는 메소드"""
        res_str = "|"

        # 링크드  리스트 안에 모든 노드를 돌기 위한 변수. 일단 가장 앞 노드로 정의한다.
        iterator = self.head

        # 링크드  리스트 끝까지 돈다
        while iterator is not None:
            # 각 노드의 데이터를 리턴하는 문자열에 더해준다
            res_str += " {} |".format(iterator.data)
            iterator = iterator.next # 다음 노드로 넘어간다

        return res_str
    
    

# 새로운 링크드 리스트 생성
linked_list = LinkedList()

# 여러 데이터를 링크드 리스트 마지막에 추가
linked_list.append(2)
linked_list.append(3)
linked_list.append(5)
linked_list.append(7)
linked_list.append(11)

# 데이터 2를 갖는 노드 탐색
node_with_2 = linked_list.find_node_with_data(2)

if not node_with_2 is None:
    print(node_with_2.data)
else:
    print("2를 갖는 노드는 없습니다")

# 데이터 11을 갖는 노드 탐색
node_with_11 = linked_list.find_node_with_data(11)

if not node_with_11 is None:
    print(node_with_11.data)
else:
    print("11를 갖는 노드는 없습니다")

# 데이터 6 갖는 노드 탐색
node_with_6 = linked_list.find_node_with_data(6)

if not node_with_6 is None:
    print(node_with_6.data)
else:
    print("6을 갖는 노드는 없습니다")

prepend: 링크드 리스트 가장 앞 삽입

class Node:
    """링크드 리스트의 노드 클래스"""
    def __init__(self, data):
        self.data = data  # 실제 노드가 저장하는 데이터
        self.next = None  # 다음 노드에 대한 레퍼런스


class LinkedList:
    """링크드 리스트 클래스"""
    def __init__(self):
        self.head = None  # 링크드 리스트의 가장 앞 노드
        self.tail = None  # 링크드 리스트의 가장 뒤 노드

    def prepend(self, data):
        """링크드 리스트의 가장 앞에 데이터 삽입"""
        # 코드를 쓰세요

    def __str__(self):
        """링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
        res_str = "|"

        # 링크드 리스트 안에 모든 노드를 돌기 위한 변수. 일단 가장 앞 노드로 정의한다.
        iterator = self.head

        # 링크드 리스트 끝까지 돈다
        while iterator is not None:
            # 각 노드의 데이터를 리턴하는 문자열에 더해준다
            res_str += f" {iterator.data} |"
            iterator = iterator.next  # 다음 노드로 넘어간다

        return res_str
    
    def prepend(self, data):
        """링크드 리스트의 가장 앞에 데이터 삽입"""
        new_node = Node(data)   # 새로운 노드를 만든다
        
        # 링크드 리스트가 비었는지 확인
        if self.head is None:
            self.tail = new_node
        else:
            new_node.next = self.head  # 새로운 노드의 다음 노드를 head 노드로 정해주고
                
        self.head = new_node  # 리스트의 head_node를 새롭게 삽입한 노드로 정해준다

# 새로운 링크드 리스트 생성
linked_list = LinkedList()

# 여러 데이터를 링크드 리스트 앞에 추가
linked_list.prepend(11)
linked_list.prepend(7)
linked_list.prepend(5)
linked_list.prepend(3)
linked_list.prepend(2)

print(linked_list)  # 링크드 리스트 출력

# head, tail 노드가 제대로 설정됐는지 확인
print(linked_list.head.data)
print(linked_list.tail.data)

popleft: 링크드 리스트 가장 앞 삭제

class Node:
    """링크드 리스트의 노드 클래스"""
    def __init__(self, data):
        self.data = data  # 실제 노드가 저장하는 데이터
        self.next = None  # 다음 노드에 대한 레퍼런스
        
        
class LinkedList:
    """링크드 리스트 클래스"""
    def __init__(self):
        self.head = None  # 링크드 리스트의 가장 앞 노드
        self.tail = None  # 링크드 리스트의 가장 뒤 노드
  
    def pop_left(self):
        """링크드 리스트의 가장 앞 노드 삭제 메소드. 단, 링크드 리스트에 항상 노드가 있다고 가정한다"""
        data = self.head.data  # 삭제할 노드를 미리 저장해놓는다
    
        # 지우려는 데이터가 링크드 리스트의 마지막 남은 데이터일 때
        if self.head is self.tail:
            self.head = None
            self.tail = None
        else: 
            self.head = self.head.next
    
        return data  # 삭제된 노드의 데이터를 리턴한다
    def prepend(self, data):
        """링크드 리스트의 가장 앞에 데이터 삽입"""
        new_node = Node(data)  # 새로운 노드를 만든다

        # 링크드 리스트가 비었는지 확인
        if self.head is None:
            self.tail = new_node
        else:
            new_node.next = self.head  # 새로운 노드의 다음 노드를 head 노드로 정해주고

        self.head = new_node  # 리스트의 head_node를 새롭게 삽입한 노드로 정해준다

    def __str__(self):
        """링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
        res_str = "|"

        # 링크드 리스트 안에 모든 노드를 돌기 위한 변수. 일단 가장 앞 노드로 정의한다.
        iterator = self.head

        # 링크드 리스트 끝까지 돈다
        while iterator is not None:
            # 각 노드의 데이터를 리턴하는 문자열에 더해준다
            res_str += f" {iterator.data} |"
            iterator = iterator.next # 다음 노드로 넘어간다

        return res_str
    
    

# 새로운 링크드 리스트 생성
linked_list = LinkedList()

# 여러 데이터를 링크드 리스트 앞에 추가
linked_list.prepend(11)
linked_list.prepend(7)
linked_list.prepend(5)
linked_list.prepend(3)
linked_list.prepend(2)

# 가장 앞 노드 계속 삭제
print(linked_list.pop_left())
print(linked_list.pop_left())
print(linked_list.pop_left())
print(linked_list.pop_left())
print(linked_list.pop_left())

print(linked_list)  # 링크드 리스트 출력
print(linked_list.head)
print(linked_list.tail)

저작자표시

'소프트웨어융합 > 코드잇 정리.py' 카테고리의 다른 글

git (0)	2022.03.11
html (0)	2022.02.06
파이썬 - 폴더관리 예시제들 (0)	2022.01.30
파이썬, 문자열갖고놀기 (0)	2022.01.29
파일다루기 - 출력방식연구 (0)	2022.01.28

'소프트웨어융합/코드잇 정리.py' Related Articles