링크드리스트

1. 링크드 리스트(Linked List)

• 데이터를 순서대로 저장(정적 배열, 동적 배열)
• 데이터를 계속 추가할 수 있다(동적 배열)
• 특정 데이터를 찾기 위해 순차 탐색
• 노드에 데이터를 저장하고 각 노드들을 순서대로 연결시켜 사용
  

2. 구성

• 노드
  => Data와 Next로 이뤄짐
• Data 속성: 데이터를 넣을 수 있는 속성
• Next 속성: 다음 노드에 대한 레퍼런스
• 각 노드는 이름을 가지고 있으며 저장 데이터, 다음 노드의 레퍼런스를 가지고 있다. 각 노드는 흩어져 있지만 다음 노드 레퍼런스를 따라 순서대로 연결지어짐

링크드 리스트는 처음 시작점을 head 노드라 부르고 시작점을 기준으로 다음 노드를 연결시켜 배열같이 순서를 지정할 수 있다,

• Head 노드를 시작점으로 흩어져있는 다른 노드들을 연결지어 순서를 저장함
• 실제론 그림같이 노드들이 메모리상 순서대로 정렬되어 있는 것이 아닌 여기저기 흩어져있음

링크드 리스트(파이썬 ver) 예시

3. 추가연산

• 링크드 리스트 맨 끝에 노드 정보를 추가하는 메소드

    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

4. 접근연산

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

int arr[0] = 1

• 링크드 리스트: 특정 위치에 있는 노드를 리턴하는 연산
  => head 노드부터 시작하여 다음 노드들을 하나씩 돌며 원하는 위치의 노드에 접근

• 배열은 인덱스를 이용해서 데이터가 저장된 주소를 계산할 수 있지만, 링크드 리스트는 레퍼런스를 통해 순서를 저장하기 떄문에 한번에 원하는 위치의 데이터에 접근할 수 없다.
  => 인덱스 x 에 있는 노드에 접근하려면 head 에서 다음 노드로 x번 이동 필요

def find_node_at(self,index): ## 접근 연산 메소드. 
	iterator = self.head
        for i in range(index):
            iterator = iterator.next
        return iterator

• 시간복잡도 : O(n)
  => 인덱스를 이용하여 노드에 접근하는 것은 배열에 비해 효율적이지 못하다.

5. 탐색연산

• 자료구조에서 원하는 조건의 데이터를 찾아내는 연산
• 배열: 첫 번째 인덱스부터 마지막 인덱스까지 돌며 탐색(선형적)
• 링크드 리스트: 가장 앞 노드부터 마지막 노드까지 돌며 탐색(선형적)

    def find_node_with_data(self, data):
        """
        배열의 탐색 연산 : 선형적으로 가장 앞부터 마지막 인덱스까지 돌면서 탐색을 한다.
            => 링크드 리스트도 배열과 마찬가지로 선형 탐색을 한다. 가장 앞 노드부터 끝 노드까지 돌면서 원하는 데이터를 갖는 노드를 리턴한다.
        링크드 리스트의 탐색 연산 : 특정 데이터를 갖는 노드를 리턴한다.
        """
        iterator = self.head           # 링크드 리스트의 모든 노드를 돌기 위한 변수. 처음에는 head로 초기화한다.
        while iterator is not None:    # 링크드 리스트 전체를 다 돈다.
            if iterator.data == data:  # 링크드 리스트에 원하는 데이터 값을 찾은 경우
                return iterator        # 그 데이터가 있는 노드를 리턴한다
            iterator = iterator.next   # 다음 노드로 넘어가며 탐색하기 위해 iterator에 다음 노드를 저장해준다.
        return None                    # 링크드 리스트에 원하는 데이터 값이 없는 경우 리턴할 노드가 없으므로 None 을 리턴한다.

6. 삽입연산

• 기존 링크드 리스트의 노드 뒤에 새로운 노드를 추가하는 메서드

    def insert_after(self, previous_node, data):
        """링크드 리스트 주어진 노드 뒤 삽입 연산 메소드"""
        new_node = Node(data)
        # CASE1) 링크드 리스트 가장 마지막 순서에 삽입할 때. 즉, previous_node가 tail 노드 일때
        # CASE2) 두 노드 사이에 삽입할 때
        if self.tail == previous_node:
            self.tail.next = new_node
            self.tail = new_node
        else:
            new_node.next = previous_node.next  # new_node의 다음 노드가 prvious_node의 다음 노드가 되게 한다.
            previous_node.next = new_node       # previous_node 의 다음 노드로 새로 삽입하는 노드인 new_node 를 설정해준다.     

• 링크드 리스트의 가장 앞에 데이터 삽입

    def prepend(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node

7. 삭제연산

• 구현 예시
  

• 주어진 노드 뒤 노드를 삭제한다.

def delete_after(self, previous_node)
    if previous_node.next is self.tail:
    	previous_node.next = None
        self.tail = previous_node
    else:
    	previous_node.next = previous_node.next.next