[자료구조] 선형리스트 - 정의, ADT

📰 선형리스트

• 정의
  • 순서를 가진 원소들의 순열
  • 물리적 순서가 아닌 원소의 특성에 의한 논리적 순서를 의미
  • 리스트는 기본적으로 순서 개념을 가지므로 선형 리스트라고 볼 수 있음

💡 리스트 : 원소들의 순열로써 원소들을 일렬로 나열해 놓은 것

• 표현
  • 배열을 이용해 표현함
  • 삽입, 삭제 시 후속 원소들을 한 자리씩 밀거나 당겨야하는 오버헤드 발생

📰 선형리스트 ADT

• object
  • L = (e1, e2, e3 .. en) 으로 표기
  • L은 리스트 이름, e는 리스트 원소
  • L = () : 공복 리스트의 표현
  • 리스트의 각 원소는 선행자와 후속자를 가짐
• function
  • createList() : 공백리스트 L 생성
  • isEmpty(L) : 리스트 L이 공백인지 아닌지 알려줌
  • length(L) : 리스트 L의 길이 반환. (리스트 길이 = 리스트에 포함된 원소의 수)
  • retrieve(L, i) : 리스트 L의 i번째 원소 검색
  • replace(L, x, y) : 리스트 L의 원소 x를 새로운 원소 y로 대체
  • delete(L, x) : 공백이 아닌 리스트 L로부터 원소 x 제거, 리스트 길이 1 감소
  • insert(L, i, x) : 새로운 원소 x를 리스트 L의 지정된 위치 i에 삽입, 리스트 길이 1 증가