프로그래머스 강의_7

연결 리스트(Linked Lists)

추상적 자료구조(Abstract Data Structures)

• Data ( 예 : 정수, 문자열, 레코드,...)
• A set of operations (삽입, 삭제, 순회, 정렬, 탐색, ...)

  기본적 연결 리스트

• 각각의 아이템 : Node ( Data, Link (next) )
  Node 내의 데이터는 다른 구조로 이루어질 수 있음 (문자열, 레코드, 또다른 연결리스트 등..)
• Head , Tail, of nodes : 3..

class Node :
   def __init__(self, itme) :
        self.data = item
        self.next = None

- 비어있는 연결 리스트
class LinkedList:
    def __init__(self) :
       self.nodeCount = 0
       self.head = None
       self.tail = None

연산 정의

1. 특정 원소 참조(k번째)
   0으로 사용하는 인덱스를 사용하지 않고 1, 2, 3으로 시작한다.
   0은 다른 목적으로 사용하기위해서 빼놓고 시작한다.

   pos를 가지고 pos번째에 있는 노드를 뽑아서 노드 자체를 리턴하는 함수.
   def getAt(self,pos):
      if pos<=0 or pos>self.nodeCount:
      return None
      
      i = 1
      curr = self.head
      while i < pos:
          curr = curr.next
          i += 1 
      return curr 
      i는 1부터 post와 같아지면 현재를 리턴한다.

배열과 비교한 연결 리스트
배열 < 연속한 위치에 저장, 인덱스로 찾을 수 있다.> O(1)
연결 리스트 < 링크로 연결되었기 때문에 임이의 위치에 저장되어있다. 선형탐색과 유사> O(n)

연습 문제

traverse()는 리스트를 리턴하되, 이 리스트에는 연결 리스트의 노드들에 들어 있는 데이터 아이템들을 연결 리스트에서의 순서와 같도록 포함한다.