---

추상자료형

ADT(Abstract Data Type)
: 추상자료형, 데이터구조의 추상형
: 실제 존재하는 개념을 내가 원하는 자료형으로 만드는 것

---

리스트 ADT

rank(순위)
: 리스트 ADT에서 원소에 접근할 때 필요한 도구

리스트 ADT 메소드

일반메소드

boolean isEmpty() {true(1) or false(0)}
integer size()
iterator elements()

접근메소드

element get(r)

갱신메소드

element set(r,e)  {r:위치, e: 원소}
add(r,e)
addFirst(e)
addLast(e)

element remove(r)
element removeFirst()
element removeLast()

---

예외

invalidRankException()
: 유효하지 않은 rank에 접근했을 때

fullListException()
: 더 이상 공간이 없는데 add하려 할 때

emptyListException()
: 리스트 안에 아무 것도 없는데 remove하려 할 때

---

리스트 응용

리스트 ADT
: 원소들의 순서(ordered) 집단을 저장하기 위한 데이터구조

예를 들어 스택, 큐, 집합 등이 있다

---

1 배열을 이용한 구현

• 배열의 크기 $N$
• 배열의 속한 원소의 수 $n$
• rank는 $0$에서 출발
• get(r), set(r,e) -> $O(1)$ 걸림

---

초기화(initialization)

$O(1)$ 시간 소요

Alg initialize()
	input array V, integer N
    output an empty array V of size of n

1. n<-0
2. return

---

순회(traversal)

$O(n)$ 시간 소요

• $V[0], V[1], ..., V[n-1]$ 방문

Alg traverse()
	input array V, integer N, n
    output none
1. for r<-0 to n-1
	visit(V[r])       {print,etc}
2. return

---

삽입(insertion)

최악의 경우$(r=0)$ -> $O(n)$ 시간 소요

$add(r,e)$에서 $r$자리에 새 원소 $e$를 넣기 위해
$V[n-1],...,V[r]$ (n-1개) 원소들을 순방향으로 이동

Alg add(r,e)
	input array V, integer N, n, rank r, element e
    output none

1. if(N == n)
	fullListException()
2. for((r<0) || (r>n))
	invalidRankException()
3. for i<-n-1 downto r
	V[i+1] <- V[i]
4. V[r] <- e
5. n <- n+1
6. return

---

삭제(deletion)

최악의 경우$(r=0)$ -> $O(n)$ 시간 소요

$remove(r)$에서 빈 자리를 채우기 위해 $V[r+1],...,V[n-1]$ 원소들 역방향으로 이동

Alg remove(r)
	input array V, integer N,n, rank r
    output element e

1. if((r<0) || (r>n))
	invalidRankException()
2. e <- V[r] {나중에 return을 위해 저장해놓음}
3. for i <- r+1 to n-1
	V[i-1] <- V[i]
4. n <- n-1
5. return e

---

성능(performance)

배열을 이용하여 리스트ADT 구현할 경우

• size, isEmpty, get, set: $O(1)$
• add, remove: $O(n)$
• addFirst, removeFirst: $O(n)$
• addLast, removeLast: $O(1)$

if 배열이 원형이라면

• addFirst, removeFirst: $O(1)$
  포인터 f(first)와 l(last)를 옮겨주면 되니까

---

2 연결리스트를 이용한 구현

2-1 단일 연결리스트

단일연결리스트
: 노드가 단위이고 노드가 연속으로 구성된 데이터구조

노드의 저장 내용
: 원소(element)
: 다음 노드를 가리키는 링크(link)

rank는 $1$에서 출발

struct Node{
	char elem;
    struct Node *next; //자기참조구조체
}

단일 연결리스트를 이용한 구현

Alg get(r)
	input a sinlge linked list and rank r
    output element

1. if((r<1) || (r>n))
		invalidRankException()
2. p <- H
3. for i<- 1 to r-1
		p <- p.next;
4. return p.elem

Alg set(r,e)
	input a single linked list rank r, element e
    output element
1. if((r<1) || (r>n))
		invalidRankException()
2. p <- H
3. for i <- 1 to r-1
		p <- p.next
4. p.elem <- e
5. return e

위의 의사코드에서 조금 생각해야 하는 부분은
r이 아니라 r-1까지만 for문을 반복해야 한다는 것이다!

그 이유는 r-1 포인터가 다음 노드의 element값을 가리키기 때문

• 이중연결리스트와 헷갈리지 말아야 할 부분은
  그때는 우리가 헤더 노드를 사용했고 여기서는 포인터를 사용하고 있다는 거야.
  (이것 때매 계속 헷갈림)

[chatgpt의 도움]

• 단일 연결 리스트: 각 노드가 다음 노드를 가리키는 포인터만을 가집니다. 따라서 p 포인터를 헤더 노드에서 출발하여 r-1번째 노드까지 이동해야 r번째 원소에 도달합니다.

• 이중 연결 리스트: 각 노드가 이전 노드와 다음 노드를 가리키는 두 개의 포인터를 가집니다. 따라서 p 포인터를 헤더 노드에서 출발하여 r번째 노드까지 이동해야 r번째 원소에 도달합니다.

---

초기화

$O(1)$ 시간 소요

Alg initialize()
	input none
    output an empty single linked list
1. H <- NULL
2. n <- 0
3. return

---

순회

$O(n)$ 시간 소요

Alg traverse()
	input a single linked list
    output none
1. p<-H
2. while(p≠NULL)
	visit(p.elem)
    p <- p.next
3. return

---

삽입

$O(n)$ 시간 소요

Alg add(r,e)
	input a single linked list with rank r, element e
    output none

1. if((r<1) || (r>n))
		invalidRankException()
2. p <- H
3. for i <- 1 to r-2
		p<-p.next
4. addNode(p,e)
5. n<-n+1
6. return

여기서 넣으려는 위치보다 하나 전으로 가야 하니까 위의 문제처럼 (r-1)가 아니라 (r-2)

Alg addNode(p,e)
	input a single linked list with node p, element e
    output none

1. q <- getNode()
2. q.elem <- e
3. if(p == NULL)
		q <- p
4. Else
	q.next <- p.next
    p.next <- q
5. return

---

삭제

$O(n)$ 시간 소요

Alg remove(r)
	input a single linked list with rank r
    output element
    
1. if((r<1) || (r>N))
    	invalidRankException()
2. p <- H
3. for i <- 1 to r-2
		p<-p.next
4. e <- removeNode(p)
5. return e

Alg removeNode(p)
	input a single linked list with node p
    output element

1. q <- p.next
2. e <- q.elem
3. p.next <- q.next
4. putNode(q)         {reuse}
5. return e

---

2-2 이중연결리스트

노드의 필드

• 원소
• 이전 노드를 가리키는 링크
• 이후 노드를 가리키는 링크

헤더 및 트레일러 노드

rank는 $1$에서 출발

---

이중연결리스트를 이용한 구현

Alg get(r)
	input a doubly linked list with header H and trailer T, rank r
    output element

1. p <- H
2. for i<-1 to r
		p<-p.next
3. return p.elem

Alg set(r,e)
	input a doubly linked list with header H and trailer T, rank r, element e
    output element
    
1. p <- H
2. for i <- 1 to r
		p <- p.next
3. p.elem <- e
4. return e

L과 H는 항상 복사해서 사용할 것

---

초기화

$O(1)$ 시간 소요

Alg initialize()
	input none
    output an empty doubly linked list
1. H <- getNode()       {노드할당}
2. T <- getNode()       {노드할당}
3. H.next <- T
4. T.prev <- H
5. n <- 0
6. return

---

순회

$O(n)$ 시간 소요

Alg traverse()
	input a doubly linked list with header H and trailer T
    output nonde

1. p <- H.next
2. while(p≠ T)
		visit(p.elem)
        p <- next
3. return

---

삽입

$O(n)$ 시간 소요

Alg add(r,e)
	input a doubly linked list with header H and trailer T, rank r, element e
    output none

1. if((r<1) || (r>n))
		invalidRankException()
2. p <- H
3. for i<- 1 to r
	p <- p.next
4. addNodeBefore(p,e)
5. n <- n+1
6. return

Alg addNodeBefore(p,e)
	input a doubly linked list with header H and trailer T, node p, element e
    output none

1. q <- getNode()
2. q.elem <- e
3. q.prev <- p.prev
4. q.next <- p
5. (p.prev).next <- q
6. p.prev <- q
7. return

---

삭제

$O(n)$ 시간 소요

Alg remove(r)
	input a doubly linked list with header H, trailer T, rank r
    output element

1. if((r<1) || (r>n))
		invalidRankException()
2. p <- H
3. for i <- 1 to r
		p <- p.next
4. e <- removeNode(p)
5. return

Alg removeNode(p)
	input a doubly linked list with header H, trailer T, node p
    output element

1. e <- p.elem
2. (p.prev).next <- p.next
3. (p.next).prev <- p.prevv
4. putnode(p) {주소 p의 노드에 할당되었던 메모리의 사용을 해제 후 이를 동적 메모리에 반환 (메모리 재활용 위해)}
5. return e

---

성능

size, isEmpty: $O(1)$
get, set, add, remove: $O(n)$
addFirst, addLast, removeFirst, removeLast: $O(1)$

---

성능 요약