[자료구조] 연결리스트(2)

다항식 표현(Polynominal Represenation)

• 다항식(Polynominal)
  
  • ai: 0이 아닌 것.
  • E: 음의 적분 지수.

• 다항식의 표현
  

• C에서의 다항식

padd()
attatch()
erase()

• Analysis padd()

  • 이 알고리즘의 세가지 비용 측청치

    1. 계수 추가
       
       0 ≤ 계수 추가 횟수 ≤ min{m, n}

    2. 지수 비교

    • While 루프의 각 반복에 대한 한 번의 비교
    • 반복 횟수는 m + n으로 제한된다.
      ex) m+n-1 반복: 식 = n 및
    3. c에 대한 새 노드 생성
    • c의 최대 항 수는 m + n입니다

=> (1)부터 (3)까지, 총 시간 복잡도는 O(m + n) 이다.

이중 연결 리스트(Double Linked List)

• 단순 연결 리스트(chain)의 문제점
  • 선행 노드를 찾기가 힘들다
    -> 특정 노드 p 또는 노드 p 앞에 있는 노드를 찾는 유일한 방법은 목록의 처음부터 시작하는 것 뿐이다.
  • 삽입이나 삭제시에는 반드시 선행 노드가 필요하다

• 이중 연결 리스트는 하나의 노드가 선행 노드와 후속 노드에 대한 두개의 링크를 가지는 리스트로, 링크가 양방향 이므로 양방향 검색이 가능 하다. 그러나 공간을 많이 차지하며 코드가 비교적 복잡하다는 단점이 있다.
• 실제 사용되는 이중 연결 리스트의 형태: 헤드 노드 + 이중 연결 리스트 + 원형 연결 리스트
  
  • 헤드 노드(head node): 데이터를 가지지 않고 단지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드. 헤드 포인터와의 구별이 필요하며 공백 상태에서는 헤드 노드만 존재한다.

이중 연결 리스트에서의 노드의 구조

• ptr이 이중으로 연결된 목록의 임의의 노드를 가리키면
  ptr = ptr->llink->rlink = ptr->rlink->link 이 공식을 반영한다.
• 이 공식은 우리가 앞 뒤 똑같은 난이도로 접근할 수 있다는 사실을 알려준다.
  

삽입 연산(Dinsert())

삭제 연산(Ddelete())