TIL_33 : 링크드 리스트

🙄 링크드 리스트 (Linked List)

---

➡ 링크드 리스트란?

• 노드라는 단위의 데이터를 저장
• 데이터가 저장된 각 노드들을 순서대로 연결시켜서 만든 자료 구조
• 데이터를 순서대로 저장해준다
• 요소를 계속 추가할 수 있다

👉 동적 배열 보다 복잡한 구현 방식
👉 상황에 따라 링크드 리스트, 동적 배열 사용

➡ 노드 (Node)

• 두 가지 속성
  1. data : 저장하고 싶은 정보를 넣음
  2. next : 다음 노드에 대한 레퍼런스

• 가장 첫 번째 노드 객체의 메모리 주소만 알면 next를 타고 연결된 모든 노드에 접근 가능

• head 노드 : 첫 번째 노드

👉 실제 메모리에는 여기저기 흩어져 있다

🙄 링크드 리스트 만들기

---

➡ 노드 클래스 만들기

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

# 데이터 2, 3, 5, 7, 11을 담는 노드를 생성
head_node = Node(2)
node_1 = Node(3)
node_2 = Node(5)
node_3 = Node(7)
tail_node = Node(11)

👉 아직은 메모리에 흩어져 있는, 서로 관계없는 Node들

➡ 간단한 링크드 리스트 만들기

# 노드들을 연결
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
    
# 2
# 3
# 5
# 7
# 11

🙄 링크드 리스트 연산

---

➡ 링크드 리스트 추가 연산

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

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

# 링크드 리스트에 데이터 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)
my_list.append(11)

# 링크드 리스트 출력
iterator = my_list.head

while iterator is not None:
    print(iterator.data)
    iterator = iterator.next
    
# 2
# 3
# 5
# 7
# 11    

링크드 리스트 __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 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

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

# 링크드 리스트에 데이터 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)
my_list.append(11)

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

# | 2 | 3 | 5 | 7 | 11 |

➡ 링크드 리스트 접근

배열 접근 연산

• 특정 위치에 저장한 데이터를 가지고 오거나 바꿔주는 연산

링크드 접근 연산

• 특정 위치에 있는 노드를 리턴하는 연산
• 인덱스 $x$에 있는 노드에 접근하려면 head 에서 다음 노드로 $x$번 가면 됨

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_at(self, index):
        """링크드 리스트 접근 연산 메소드, 파라미터 인덱스는 항상 있다고 가정"""
        iterator = self.head

        for _ in range(index):
            iterator = iterator.next

        return iterator


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

# 링크드 리스트에 데이터 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)
my_list.append(11)

# 링크드 리스트 노드에 접근 (데이터 가지고 오기)
print(my_list.find_node_at(3).data)

# 링크드 리스트 노드에 접근 (데이터 바꾸기)
my_list.find_node_at(2).data = 13

# 전체 링크드 리스트 출력
print(my_list)

# 7
# | 2 | 3 | 13 | 7 | 11 |

링크드 리스트 접근 시간 복잡도

• 인덱스 $x$에 있는 노드에 접근하려면 head 에서 다음 노드로 $x$번 가면 됨
• 마지막 노드에 접근하려면 head 에서 다음 노드로 $n-1$ 번 가야 됨
• 접근 연산 시간 복잡도 : $O(n)$

➡ 링크드 리스트 삽입 연산

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

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


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

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

    def insert_after(self, previous_node, data):
        """링크드 리스트 주어진 노드 뒤 삽입 연산 메소드"""
        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

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

        for _ in range(index):
            iterator = iterator.next

        return iterator

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

        while iterator is not None:
            res_str += f" {iterator.data} |"
            iterator = iterator.next   

        return res_str

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

# 링크드 리스트에 데이터 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)

print(my_list)

node_2 = my_list.find_node_at(2) 	# 인덱스 2에 있는 노드 접근
my_list.insert_after(node_2, 6) 	# 인덱스 2 뒤에 6 삽입

print(my_list)

head_node = my_list.head 		# 헤드 노드 접근
my_list.insert_after(head_node, 9) 	# 헤드 노드 뒤에 9 삽입

print(my_list)

# | 2 | 3 | 5 | 7 |
# | 2 | 3 | 5 | 6 | 7 |
# | 2 | 9 | 3 | 5 | 6 | 7 |

➡ 링크드 리스트 삭제 연산

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

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


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

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

    def delete_after(self, previous_node):
        """링크드 리스트 삭제 연산, 주어진 노드 뒤 노드를 삭제한다"""
        data = previous_node.next.data  # 지우는 노드의 데이터를 리턴하는 것이 관습

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

        return data

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

        for _ in range(index):
            iterator = iterator.next

        return iterator

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

        while iterator is not None:
            res_str += f" {iterator.data} |"
            iterator = iterator.next    

        return res_str

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

# 링크드 리스트에 데이터 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)
my_list.append(11)

print(my_list)

node_2 = my_list.find_node_at(2) 	# 인덱스 2 노드 접근
my_list.delete_after(node_2)    	# 인덱스 2 뒤 데이터 삭제

print(my_list)

second_to_last_node = my_list.find_node_at(2)		# 맨 끝에서 두 번째 노드 접근
print(my_list.delete_after(second_to_last_node)) 	# tail 노드 삭제

print(my_list)

# | 2 | 3 | 5 | 7 | 11 |
# | 2 | 3 | 5 | 11 |
# 11							# 지워지면서 data 리턴
# | 2 | 3 | 5 |

🙄 링크드 리스트 시간 복잡도

---

시간 복잡도

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

• 삽입, 삭제는 인덱스의 주변 노드들에 연결된 레퍼러스만 수정
  ➡ 어떤 순서에 있는 노드든 상관없이 일정한 시간 소요 = $O(1)$

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

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

• 삽입과 삭제 연산들은 특정 노드를 넘겨줘야 함
• head 와 tail 노드는 저장되어있지만 나머지 노드들은 탐색, 접근 연산으로 가져옴
• 삽입과 삭제 연산은 접근 또는 탐색의 시간 복잡도인 $O(n)$를 공유한다고 볼 수 있음

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

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

• head 와 tail 노드는 접근하는데 $O(1)$, 연산을 하는데 $O(1)$
• tail 노드 삭제하기 위해서 바로 전 노드에 접근하는데 $O(n)$