리스트

리스트의 구조

Stack, Queue, Deque과의 비교

공통점: 선형 자료구조

차이점: 자료의 접근 위치

리스트의 연산

• 기본 연산
  • 리스트의 어떤 위치에 새로운 요소를 삽입한다.
  • 리스트의 어떤 위치에 있는 요소를 삭제한다.
  • 리스트의 어떤 위치에 있는 요소를 반환한다.
  • 리스트가 비었는지를 살핀다.
  • 리스트가 가득 차있는지를 체크한다.
• 고급 연산
  • 리스트에 어떤 요소가 있는지를 살핀다.
  • 리스트의 어떤 위치에 있는 요소를 새로운 요소로 대치한다.
  • 리스트 안의 요소의 개수를 센다.
  • 리스트 안의 모든 요소를 출력한다.

리스트 ADT

데이터: 임의의 접근 방법을 제공하는 같은 타입 요소들의 순서 있는 모임
연산:
▪ insert(pos, item): 리스트의 pos 위치에 새로운 요소 item을 삽입한다.
▪ remove(pos): 리스트의 pos 위치에 있는 요소를 삭제한다.
▪ getEntry(pos): 리스트의 pos 위치에 있는 요소를 반환한다.
▪ isEmpty(): 리스트가 비어있는지를 검사한다.
▪ isFull(): 리스트가 가득 차 있는지를 검사한다.
▪ find(item): 리스트에 요소 item이 있는지를 살핀다.
▪ replace(pos, item): pos 위치에 있는 요소를 새로운 요소 item으로 바꾼다.
▪ size(): 리스트 안의 요소의 개수를 반환한다.
▪ display(): 리스트 안의 모든 요소들을 출력한다.

 

리스트 구현 방법

• 배열을 이용
  • 구현이 간단
  • 삽입, 삭제 시 오버헤드
  • 항목의 개수 제한
• 연결리스트를 이용
  • 구현이 복잡
  • 삽입, 삭제가효율적
  • 크기가 제한되지 않음

공백상태 / 포화상태

주요 연산

• 삽입연산
  • 삽입위치 다음의 항목들을 이동하여야 함.
• 삭제연산
  • 삭제위치 다음의 항목들을 이동하여야 함

연결 리스트로 구현한 리스트

• 단순 연결 리스트(simply linked list) 사용
  • 하나의 링크 필드를 이용하여 연결
  • 마지막 노드의 링크 값은 NULL

리스트의 삽입 연산

insert(before, node)

 

if isEmpty()

  then head <- node

  else node.link <- before.link

        before.link  <- node

리스트의 삽입 삭제

remove(before)

 

if isEmpty() = false

  then  removed <- before.link

          before.link ← removed.link

          destroy(removed)

헤드 포인터와 헤드 노드

헤드 노드: 포인터 변수가 아니라 Node 객체

맨 앞 노드의 삽입이나 삭제 연산을 단순화할 수 있음

단순리스트를 이용한 구현

단순연결리스트 vs. 이중 연결 리스트

• 단순연결리스트
  • 후속 노드는 쉽게 알 수 있다.(링크 필드)
  • 선행 노드를 알 수는 없을까?
  • 헤드포인터에서부터 리스트 항목들 탐색 필요
• 이중연결리스트(doubly linked list)
  • 특정노드에서 양방향으로 자유롭게 움직일 필요가 있을 때 이중연결리스트를 사용
  • 공간을 더 많이 차지하고 코드가 복잡해 짐

이중 연결 리스트