연결 리스트의 추상 자료형

---

연결 리스트를 구현하기 이전, 연결 리스트의 추상 자료형을 알아보도록 하자.

ADT Linked List
    자료 : 순서를 가지고 저장되어 있는 n개의 요소
    연산 :
        - create() ::= 연결 리스트를 만드는 연산
        - add(list, p, e) ::= p 위치 다음에 요소 e를 추가하는 연산
        - delete(list, p) ::= p 위치의 요소를 삭제하는 연산
        - isEmpty(list) ::= 리스트가 비었는지를 검사하는 연산
        - isFull(list) ::= 리스트가 꽉 찼는지를 검사하는 연산

연결 리스트의 삽입 연산

---

위와 같이 연산을 하는 것이 바로 연결리스트에서 삽입 연산으로 생각할 수 있다.

이를 알고리즘(의사 코드)으로 나타내면 아래와 같다.

add(list, p, e)
    if list = NULL then list ← e // 리스트에 아무것도 없을 경우 e가 첫 노드가 됨
    else
        e.link ← p.link // 리스트에 인수가 있을 경우 p노드 포인터가 e노드를 가리킨다
        p.link ← e // e를 p노드에 연결시킨다
end add()

조금 더 정확한 이해를 위해 바로 이해가 안 되는 부분인 e.link ← p.link 부분과 p.link ← e 부분에 대해 그림과 함께 이해해보자.

연결 리스트의 삭제 연산

---

연결 리스트의 삭제 연산은 위의 그림과 같다.

이를 알고리즘, 즉 의사코드로 나타내면 아래와 같다.

delete(list,p)
    if list ≠ NULL
    then p.link ← e.link // e에 연결되어 있는 것을 p에 연결
end delete()

참고

---

정관용, 임종범, 박병기, 복대원. (2013). 고등학교 정보과학 (pp. 206-207). 서울: (주)현대아트컴.