일반 리스트

최종 수정 : 24.12.27

일반 리스트

1. 정의

일반 리스트는 0개 이상의 원소 또는 서브 리스트를 가지는 유한 리스트이다. 일반 리스트 표현은 L = (e1, e2, e3, ..., en)으로 하고, L은 리스트의 이름이며, n은 리스트 내에 원소의 개수를 의미한다. n ≥ 1인 경우의 첫 번째 원소는 L의 head이며 head(L)이라 표현한다. 첫 원소(head)를 제외한 나머지 리스트를 L의 tail이라 하며 tail(L)이라 표현한다.

 

ex) A = (a, (b, c))

• 길이 : 2
• head(A) = a, tail(A) = ((b,c))

아래 그림은 일반 리스트의 노드 구조를 나타낸다. tag 필드는 data 필드 값이 원자인지 포인터 값인지를 표시하며 data 값이 원잣값이면 tog는 0이고, data 값이 서브 리스트에 대한 포인트 값이면 tag는 1로 표현한다. data 필드는 리스트의 head를 저장하고 head(L)이 원자인지 서브 리스트인지에 따라 원잣값 또는 서브 리스트의 포인터가 저장된다. link 필드는 리스트의 tail에 대한 포인터를 저장한다.

tag

data

link

 

일반 리스트를 표현하는 데 있어서 저장공간을 절약하기 위한 서브 리스트를 공용으로 사용하도록 표현한다. 이러한 공용 리스트 사용은 한 리스트가 어떤 리스트에 의해 참조되는지 알 수 없으므로 연산 시간이 많이 걸리는 문제점이 있다. 이러한 문제점을 해결하기 위하여 헤더 노드를 추가함으로 공용 리스트 내부에서 노드 삽입과 삭제가 일어나더라도 포인터는 영향을 받지 않는다.

---

2. 다중 변수 다항식의 일반 리스트 표현

다중 변수 다항식은 변수의 개수가 2개 이상인 경우로 다항식 F를 표현하기 위해서는 변수에 개수에 따라 노드의 구조를 달리 표현한다.

---

 

참고

독학사 교재