연결리스트

5주차

• 단일연결리스트
  • 역으로 순회하는 것이 어려움
• 이중연결리스트
  • 구성
    • 이전 노드를 가리키는 링크
    • 원소
    • 다음 노드를 가리키는 링크
  • 초기화
    • 헤더는 트레일러를,
    • 트레일러는 헤더를 가리킴
  • 순회
    • O(n) 소요
  • 삽입
    • O(n) 시간 소요

      for i <- 1 to r
      		p <- p.next
      ------------------------------------
      q.prev <- p.prev  //q->prev=p->prev 라는 뜻
      q.next <- p
      p.prev.next <- q
      p.prev <- q

  • 삭제

  •   for i <- 1 to r
              p <- p.next
      ------------------------------
      p.prev.next <- p.next
      p.next.prev <- p.prev

  • 성능: 이중연결리스트를 이용한 리스트 ADT를 구현할 경우
    • 연결리스트 각 원소에 사용되는 기억장소: O(1)
    • N개의 원소로 구성된 연결리스트에 의해 사용되는 기억장소: O(n)
    • size, isEmpty: O(1)
    • get, set, add, remove: O(n)
      • for문을 한 바퀴씩 돌아야 하기 때문: O(n)
    • addFirst, addLast, removeFirst, removeLasst: O(1)
      • node를 찾아가는 시간이 걸리지 않기 때문에 O(1)이다.
      • 그냥 Head→next, Trail→prev로 하면 됨

H.next <- p.next
p.next.prev <- H

• 원형연결리스트
  • Head가 마지막 노드를 가리키게 하는 것이 용이
  • 맨 처음에 node 추가 시
  • node->link=last->link last->link=node
  • 맨 마지막에 node 추가시
  • node->link=last->link last->link=node **last=node** //NEW!!
  • 원형 연결리스트 길이 계산

int length (listPointer last){
	listPointer temp;
	int count=0;
	if (last){
		temp=last; 
		do{
			count++;
			temp=temp->link;
		}while(temp!=last);//temp!=null 이런 식으로 쓰면 안 됨!
	}
	return count;
}

• 그룹 설계방법

A. 레코드의 리스트 사용

1. 배열을 이용한 구현
2. 연결리스트를 이용한 구현

B. sublist들의 리스트 사용

1. 2D 배열을 이용한 구현
2. 연결리스트의 배열을 이용한 구현
   • A. 레코드의 리스트 사용
     • 그룹을 표현하기 위해 elem 및 group 필드로 구성된 레코드의 리스트를 사용
     • 장점: 단순
     • 단점: 특정 그룹에 관한 작업을 위해서는 전체 레코드를 순회
       • O(n) 시간 소요 (n은 총 레코드 개수)
     1. 배열 이용
        • 레코드의 1D배열 이용(구조체 이용한 건가?)
        • 장점: 기억장소 낭비 X
        • 초기화: 아무 레코드도 X
        • 순회: 지정된 그룹의 모든 멤버들을 방문
        • 삭제: 지정된 그룹의 모든 멤버를 삭제
     2. 연결리스트 이용
        • 리스트를 elem 및 group 필드로 구성된 레코드 노드의 이중연결리스트를 이용하여 구현 가능
        • 장점: 기억장소 사용 최소화
        • 초기화: 초기에는 각 그룹에 아무 노드도 X
        • 순회: 지정된 그룹의 모든 멤버들을 방문
        • 삭제: 지정된 그룹의 모든 멤버들을 삭제
          • O(n)
     B. sublist들의 리스트 사용
     • 그룹을 표현하기 위해, 그룹의 리스트를 사용하며 각 그룹은 다시 원소들의 부리스트로 구성
     • 장점: 특정 그룹 관련 작업 격리 처리 가능
   • 2D 배열 이용
   • M * N 배열을 사용하여, 리스트는 각 그룹을 나타내는 행을, 부리스트는 각 행의 원소들을 이용하여 구현 (M은 그룹의 개수)