자료구조의 기초 2

1.   연결리스트

 

 -  연결리스트는 데이터(Data)와 링크(Link)의 두 필드로 구성되고, 링크(link)역할의 포인터 변수를 이용하여 각 원소를 링크로 연결하여 나타냅니다.

 -  연결 리스트의 장점은 중간 노드의 삽입과 삭제가 대단히 쉽고 빠르고, 기억 장소로부터 독립적이라는 것입니다. 

 - 단점으로는 포인터로 운영해야 하므로 액세스 시간이 느리고, 링크 부분만큼의 기억 공간이 소모되는 것을 들 수 있습니다.

 

 -  연결 리스트의 종류는 단순 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트 등이 있습니다.

 

2.  트리

 -  트리의 노드들은 계층적으로 가지에 의해 연결되어 경로(path)를 형성하는데, 

     그래프와는 달리 어떠한 경우에도 사이클(Cycle)을 형성하지 않습니다.

 -  트리는 그 형태나 또는 트리가 갖는 특성에 따라서 순서 트리(ordered tree), 오리엔티드 트리(oriented tree), 닮은 트리, 이진 트리(binary tree), 사향 트리(skewed tree) 등으로 나눌 수 있습니다. 

  - 트리의 순회 방법에는 전위(preorder) 순회, 중위(inorder) 순회, 후위(postorder) 순회, 패밀리오더(family order) 순회, 레벨오더(level order) 순회가 있습니다.

 

3. 그래프

  - 간선을 나타내는 정점의 쌍의 순서가 없는 그래프를 무방향 그래프(undirected graph)라 하고, 어느 한 정점에서 다른 정점으로 이어지는 간선이 화살표로 표시된 그래프를 방향 그래프(directed graph 또는 digraph)라고 합니다.