Linked List

데이터의 원소들의 순서를 지어 늘어놓는다는 점은 Linear array와 비슷한 면이 있으나 약간의 차이가 있다.

• Linear array : "번호가 붙여진 칸에 원소들을 채워넣는" 방식
• Linked list : "원소 하나하나를 줄줄이 실로 엮어넣는" 방식

Linked list는 노드(Data+Link)로 구성되어 있으며, 각 노드의 Link는 다음 노드의 Data를 가리킨다.

출처 : https://www.geeksforgeeks.org/types-of-linked-list/

   Linked List의 장점

1. 원소를 삽입하거나 삭제하기가 쉽다 (소요시간 짧음)
2. 이러한 연산이 자주 일어나는 운영체제 내부에서 많이 이용된다.

   Linked List의 단점

1. Linked list의 Data와 Link가 모두 메모리에 저장되므로 메모리 요구량이 array보다 더 크다.
2. 원소 탐색에 있어서 해당 인덱스를 알면 바로 찾을 수 있는 array에 비해서 link를 따라 하나하나 찾아야 한다.

 # 특정 원소 찾기(탐색)
def getAt(self, pos):
  if pos <= 0 or pos > self.nodeCount:
    return None

  i = 1
  curr = self.head  # head 부터 탐색 시장
  while i < pos:
    curr = curr.next
    i += 1
  return curr

 

 

	Linked List	Linear array
저장공간	임의의 위치	연속한 위치
특정 원소 지칭	선형탐색과 유사	매우 간편(인덱스)
	O(n)	O(1)

 

 

# Linked List 순회
def traverse(self):
        # 마지막 node는 None을 가리킨다.
        # 각 node는 next라는 link 값이 존재한다.
        answer = []
        current_node = self.head
        while current_node is not None:
            answer.append(current_node.data)
            current_node = current_node.next
        return answer

# 원소 삽입
def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos == 1:
            newNode.next = self.head
            self.head = newNode

        else:
            if pos == self.nodeCount + 1: # 삽입위치가 맨끝일 경우 바로 tail로 이동
                prev = self.tail
            else:
                prev = self.getAt(pos - 1)
            newNode.next = prev.next
            prev.next = newNode

        if pos == self.nodeCount + 1:
            self.tail = newNode

        self.nodeCount += 1
        return True

#원소 삭제
def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:  # 범위 밖인 경우
            raise IndexError
            
        if self.nodeCount == 1:
            curr = self.head
            self.head = None
            self.tail = None
        else:
            if pos == 1:  # 첫 번째 노드를 제거하는 경우
                curr = self.head
                self.head = curr.next
            elif pos == self.nodeCount: # 마지막 노드를 제거하는 경우
                curr = self.tail
                prev = self.getAt(pos-1)
                self.tail = prev
                prev.next = None
            else : # 중간 노드를 제거하는 경우
                prev = self.getAt(pos-1)
                curr = prev.next
                prev.next = curr.next

            # 유일한 하나의 노드를 제거하는 경우에 대하여 만족?
            # 유일한 노드란 self.head = curr, self.tail = None
            
        self.nodeCount += -1
        return curr.data

 

 

Linked List 연산의 복잡도	삽입(Insertion)	삭제(Pop)
맨 앞	O(1)	O(1)
중간	O(n)	O(n)
맨 끝	O(1)	O(n)

• Linked List는 Head와 Tail, 그리고 각 노드당 Link를 갖는다는 특성을 이용하여 연산 코드를 작성할 때
  유의해야 하며 Tail의 Link는 None이라는 점을 유의해아 한다!