카테고리 없음
[자료구조, Java] 선형 자료구조 - 1. 랜덤 접근 불가능 - 연결 리스트(Linked List)
jin-dooly
2023. 2. 23. 12:07
✅ 자료구조 : 데이터를 저장하는 방식
✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조
랜덤 접근 불가능?
모든 자료에 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의 경우 포인터 역할을 하는 레퍼런스로 구현한다.
참고
Java로 연결 리스트(Linked List) 구현하기
Java로 연결 리스트(Linked List) 구현하기 Java로 연결 리스트(Linked List)를 구현하는 방법에 대해 알아보겠습니다. 1. 연결 리스트(Linked List) 연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄
freestrokes.tistory.com
[자료구조] 그림으로 쉽게 보는 연결 리스트 (Linked List) 개념과 구현
Linked List 링크드리스트란 짧게 이야기해서 노드를 연결시킨 자료구조입니다. 노드는 무엇일까요? 링크드리스트에서 데이터를 갖고 있는 데이터의 묶음입니다. 그림으로 보는 것이 편할 것 같네
reakwon.tistory.com
연결 리스트와 배열
| 배열 | 연결 리스트 | |
| 장점 | - 값마다 인덱스를 가지기 때문에 탐색에 유리하다. | - 데이터를 삽입 또는 삭제할 때 노드만 바꿔서 연결해주면 된다. - 크기가 가변적이다. |
| 단점 | - 값마다 인덱스를 가지기 때문에 삽입이나 삭제에 불리하다. - 크기가 정해져 있어 가득 차면 사용할 수 없다. |
- 데이터의 조회가 힘들다. 각 데이터에 한번에 접근할 수가 없어서 순차적으로 접근해야된다. |
참고