참고
1. 연결 자료구조
- 연결 자료구조는 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 구현방식의 자료구조를 뜻함.
- 연결 자료구조의 원소는
노드(Node)라 불리우며 원소의 값을 저장하는데이터 필드(Data Field)와 다음 노드의 주소를 저장하는링크 필드(Link Field)로 구성.
1) 순차 자료구조와 연결 자료구조의 차이
자료구조를 떠올려보자.
각 원소들이 어떻게 배치될 것인지 머릿속으로 구상하는 것을 논리구조라 한다.
자료구조가 선언되어 실제로 메모리에 할당되어 있는 구조를 물리구조라 한다.
논리구조와 물리구조의 관점에서 연결 자료구조와 순차 자료구조의 차이를 비교해봤다.
(1) 순차 자료구조
순차 자료구조는 가장 간편한 자료 구조이며 접근 구조가 빠르다. 이는 논리적 순서와 물리적 순서가 같아 원소의 접근에 쉽기 때문이다.
하지만 삽입연산이나 삭제연산 후에 연속적인 물리적 주소를 유지하기 위해 원소들을 이동시키는 추가적인 작업과 시간이 소요된다.
때문에 원소의 개수가 많거나 삽입, 삭제 연산이 많이 필요할 경우 메모리 사용의 비효율성 문제를 가지게 된다.
(2) 연결 자료구조
연결 자료구조는 논리적 순서와 물리적 순서가 같지 않다. 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식이다.
때문에 원소의 삽입, 삭제 시 추가 작업을 할 필요가 없다.
이런 특징 덕분에 크기를 유연하게 변경할 수 있고 메모리를 효율적으로 사용할 수 있다.
2. 연결 리스트(Linked List) 내부 구조
노드(Node)라는 이름의 객체를 만들고 노드와 노드가LinkField로 연결되어 있다.- HEAD : LinkedList에서 첫번째 노드를 나타낸다.
- TAIL : LinkedList에서 제일 끝에있는 노드를 나타낸다.
- SIZE : 현재 몇개의 노드가 리스트 안에 포함되어있는가를 나타낸다.
3. 연결 리스트(Linked List)의 종류
1) 단순 연결 리스트(singly linked list)
- 다음 노드를 가리키기 위한 포인터 필드인 next만을 가지고 있는 리스트.
- 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진다.
2) 원형 연결 리스트(singly circular linked list)
- 첫번째 노드와 마지막 노드를 각각 연결시켜 리스트의 구조를 원형으로 만든 리스트.
- 링크를 따라 계속 순회하면 이전 노드에 접근 가능.
3) 이중 연결 리스트(doubly linked list)
- 기존의 단일 연결 노드 객체에서 이전 노드 주소를 담고 있는 포인터 필드인 prev가 추가된 리스트.
- 양쪽 방향으로 순회할 수 있도록 노드가 연결되는 구조를 가진다.
4) 이중원형 연결 리스트(doubly circular linked list)
- 이중 연결 리스트에서 첫번째 노드와 마지막 노드를 각각 연결시켜 리스트의 구조를 원형으로 만든 리스트.
늦깎이 애아빠 개발지망생