✅ 자료구조 : 데이터를 저장하는 방식
✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조
랜덤 접근 불가능?
모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들
연결 리스트(Linked List)
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조
노드의 포인터가 이전, 다음 노드와의 연결을 담당한다.
단일 연결 리스트(Singly Linked List)
-
각 노드가 다음 노드에 대해서만 참조하는 가장 단순한 형태의 연결 리스트
-
일반적으로 큐를 구현할 때 사용된다.
-
Head 노드를 잃어버려 참조하지 못하는 경우 데이터 전체를 사용 못하게 되는 단점이 있다
-
FAT 파일 시스템이 단일 연결 리스트로 파일 청크(동적 메모리로 할당되는 영역)를 연결합니다.(?)
이중 연결 리스트(Doubly Linked List)
-
각 노드가 이전 노드, 다음 노드에 대해서 참조하는 형태의 연결 리스트
-
삭제가 간편하며 단일 연결 리스트에 비해 데이터 손상에 강하다.
-
관리할 참조가 2개이기 때문에 삽입이나 정렬의 경우 작업량이 더 많아진다.
원형 연결 리스트(Circular Linked List)
-
연결 리스트에서 마지막 요소가 첫번째 요소를 참조
-
스트림 버퍼의 구현에 많이 사용
연결 리스트의 추상화 연산
-
addFirst(list, data) : 가장 앞에 있는 노드에 새로운 노드 추가
-
addLast(list, data) : 가장 끝에 있는 노드에 새로운 노드 추가
-
removeNode(list, data) : data 값을 가지는 노드 삭제
-
searchNode(list, data) : data의 값과 일치하는 노드 검색
-
printList() : 연결 리스트를 전부 탐색하여 출력
연결 리스트의 구현
일반적으로 구조체와 초인터로 구성되기 때문에, 포인터가 없는 java의 경우 포인터 역할을 하는 레퍼런스로 구현한다.
참고
연결 리스트와 배열
| 배열 | 연결 리스트 | |
|---|---|---|
| 장점 | - 값마다 인덱스를 가지기 때문에 탐색에 유리하다. | - 데이터를 삽입 또는 삭제할 때 노드만 바꿔서 연결해주면 된다. - 크기가 가변적이다. |
| 단점 | - 값마다 인덱스를 가지기 때문에 삽입이나 삭제에 불리하다. - 크기가 정해져 있어 가득 차면 사용할 수 없다. | - 데이터의 조회가 힘들다. - 각 데이터에 한번에 접근할 수가 없어서 순차적으로 접근해야된다. |
참고
