어소시에이션리스트

Association list
어소시에이션리스트
유형연상 배열
빅 O 표기의 시간 복잡도
알고리즘. 평균 최악의 경우
공간 O(n)O(n)
서치 O(n)O(n)
삽입 O(1)O(1)
삭제 O(n)O(n)

컴퓨터 프로그래밍, 특히 리스프(Lisp)에서 어소시에이션 리스트(alist)는, 각 리스트 요소(또는 노드)가 키와 값으로 구성되어 있는 링크 리스트입니다.어소시에이션 리스트는, 그 값을 키에 관련짓는다고 불립니다.특정 키와 관련된 값을 찾기 위해 순차 검색이 사용됩니다. 목록의 각 요소가 선두에서 시작하여 키가 발견될 때까지 차례로 검색됩니다.연관 목록은 연관 배열을 구현하는 간단한 방법을 제공하지만 키 수가 매우 적은 경우에만 효율적입니다.

작동

연관 배열은 키와 값의 쌍을 유지하고 특정 키와 관련된 값을 조회하는 데 사용할 수 있는 추상 데이터 유형입니다.연결 목록은 이 데이터 유형을 구현하는 간단한 방법을 제공합니다.

키가 특정 연관 목록 내의 값과 관련되어 있는지 여부를 테스트하려면 첫 번째 노드에서 시작하여 키를 포함하는 노드가 발견될 때까지 또는 검색이 목록의 끝에 도달할 때까지(이 경우 키가 존재하지 않음) 목록을 검색합니다.새 키와 값의 쌍을 연관지으려면 해당 키와 값 쌍의 새 노드를 만들고 해당 노드의 링크를 연관지음 목록의 이전 첫 번째 요소로 설정하고 관련지음 목록의 첫 번째 요소를 새 [1]노드로 바꿉니다.어소시에이션목록의 실장 중에는 같은 키를 가진 복수의 노드를 사용할 수 없는 것도 있습니다만, 이러한 중복은 이 검색 알고리즘에서는 문제가 되지 않습니다.목록의 후반부에 표시되는 [2]중복 키는 무시됩니다.

또한 관련 목록에서 키를 삭제할 수도 있습니다.목록을 스캔하여 키가 발생할 때마다 검색하여 [1]해당 키를 포함하는 노드를 목록에서 분리할 수도 있습니다.동일한 키가 여러 번 삽입된 경우 키가 발견되더라도 검색은 목록의 끝까지 계속됩니다.

성능

어소시에이션목록의 단점은 검색 시간이 O(n)라는 것입니다.여기서 n은 [3]목록의 길이입니다.대규모 리스트의 경우, 이것은 관련 배열을 바이너리 검색 트리 또는 해시 테이블로 나타내면 얻을 수 있는 시간보다 훨씬 느릴 수 있습니다.또한 중복된 키를 가진 요소를 제거하기 위해 정기적으로 목록을 삭제하지 않는 한 동일한 키에 관련된 값을 여러 개 지정하면 목록 크기가 증가하므로 검색 시간이 늘어나므로 보완적 이점을 얻을 수 없습니다.

어소시에이션 리스트의 장점 중 하나는 새로운 요소를 일정한 시간에 추가할 수 있다는 것입니다.또한 키 수가 매우 적은 경우 구현이 [4]훨씬 단순하기 때문에 연관 목록을 검색하는 것이 이진 검색 트리 또는 해시 테이블을 검색하는 것보다 더 효율적일 수 있습니다.

응용 프로그램 및 소프트웨어 라이브러리

Lisp의 초기 개발에서는 절차에서 [5][6]변수를 해방하기 위한 참조를 해결하기 위해 연관 목록이 사용되었습니다.이 응용 프로그램에서는 추가 조작으로 관련 목록을 증강하는 것이 편리합니다.이 조작은 같은 키의 다른 복사본에 대해 목록을 스캔하지 않고 키와 값의 쌍을 추가하는 것을 되돌립니다.이와 같이 어소시에이션리스트는 스택으로서 기능할 수 있기 때문에 로컬 변수는 다른 [7]변수의 값을 파기하지 않고 같은 이름의 다른 변수를 일시적으로 섀도우할 수 있습니다.

Lisp,[5] Scheme,[8] OCaml [9]및 Haskell을[10] 포함한 많은 프로그래밍 언어에는 표준 라이브러리에서 연관 목록을 처리하는 기능이 있습니다.

「 」를 참조해 주세요.

  • 자주 액세스하는 키의 검색 속도를 높이기 위해 연결 목록의 키를 다시 정렬하는 전략인 자체 구성 목록
  • Lisp에서 [11]사용되는 다른 연관 배열 형식인 속성 목록 또는 목록입니다.

레퍼런스

  1. ^ a b Marriott, Kim; Stuckey, Peter J. (1998). Programming with Constraints: An Introduction. MIT Press. pp. 193–195. ISBN 9780262133418.
  2. ^ Frické, Martin (2012). "2.8.3 Association Lists". Logic and the Organization of Information. Springer. pp. 44–45. ISBN 9781461430872.
  3. ^ Knuth, Donald. "6.1 Sequential Searching". The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.). Addison Wesley. pp. 396–405. ISBN 0-201-89685-0.
  4. ^ Janes, Calvin (2011). "Using Association Lists for Associative Arrays". Developer's Guide to Collections in Microsoft .NET. Pearson Education. p. 191. ISBN 9780735665279.
  5. ^ a b 매카시, 존은 에이브 럼스, 폴 W., 에드워즈, 다니엘 J., 하트, 티모시 P.;Levin, 마이클 나(1985년).리스프 1.5프로그래머의 설명서.MIT출판사.특정 페이지의 주 12에서 다른 표현으로, 우편 103조합 목록의 가변 바인딩을 유지하는 데에 응용 프로그램에 대한 기호를 대체하는 방법을 사용한 조합 목록을 검색해 기능 을 참조하십시오.
  6. ^ van de Snepscheut, Jan L. A. (1993). What Computing Is All About. Monographs in Computer Science. Springer. p. 201. ISBN 9781461227106.
  7. ^ Scott, Michael Lee (2000). "3.3.4 Association Lists and Central Reference Tables". Programming Language Pragmatics. Morgan Kaufmann. p. 137. ISBN 9781558604421.
  8. ^ Pearce, Jon (2012). Programming and Meta-Programming in Scheme. Undergraduate Texts in Computer Science. Springer. p. 214. ISBN 9781461216827.
  9. ^ Minsky, Yaron; Madhavapeddy, Anil; Hickey, Jason (2013). Real World OCaml: Functional Programming for the Masses. O'Reilly Media. p. 253. ISBN 9781449324766.
  10. ^ O'Sullivan, Bryan; Goerzen, John; Stewart, Donald Bruce (2008). Real World Haskell: Code You Can Believe In. O'Reilly Media. p. 299. ISBN 9780596554309.
  11. ^ "10.1. The Property List". Cs.cmu.edu. Retrieved 29 September 2017.