연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조다.
각 요소는 노드라고 부르며 데이터영역과 포인터 영역으로 구성된다.
메모리가 허용하는 한 요소를 제한없이 추가할 수 있다.
탐색은 O(n)이 소요된다.
요소를 추가하거나 제거할 때는 O(1)이 소요된다.
Sinlgy LInked List, Doubly linked List, Circular Linked List가 존재한다.
추가와 삭제가반복되는 로직이면 배열(순차적리스트) 대신 연결리스트가 더욱 적합하다.
https://hans-j.tistory.com/121
[알고리즘]배열(순차리스트)
배열 (Array) 연관된 데이터를 연속적인 형태로 구성된 주고를 가진다. 배열에 포함된 원소는 순서대로 번호(index)가 붙는다. 배열의 크기는 고정되어 있지 않고 가변적인 것을 명심하자!! index가 nu
hans-j.tistory.com
배열과 달리 요소 추가/삭제에 상수시간만 수행된다
Singly Linked List(단일 연결 리스트) :
Head(가장 첫번째 요소) 에서 Tail(가장 마지막 요소-포인터 영역이 Null)까지 단 방향으로 이어지는 연결 리스트. 가장 단순한 형태인 연결 리스트
단일 연결 목록은 각 노드가 두 개의 필드 'data'와 'link'를 갖는 노드 집합.
'data' 필드는 실제 정보를 저장하고 'link' 필드는 다음 노드를 가리키는 데 사용됨.
기본적으로 '링크' 필드에는 다음 노드의 주소가 저장됩니다
핵심 로직 : 요소 찾기, 추가, 삭제
헤드포인터에서 시작하여 찾고자하는 영역을 찾고 찾는값이 아닐때는 포인터를 통해 다음요소로 넘어간다.
요소 탐색(찾기)에는 O(n)(선형시간)시간이 소요된다. (추가/삭제에 걸리는 상수시간과 다른것을 기억하자!!)
추가할 요소에 포인터영역을 데이터영역의 다음에 연결시킴 -> 상수시간
삭제할 요소의 이전 포인터 영역을 삭제할 요소의 다음 데이터 영역에 연결시킴 -> 상수시간
Double LInked LIst(이중 연결 리스트) :
양방향으로 이어지는 연결 리스트
SIngly Linked List보다 자료구조의 크기가 조금 더 크다.
또한, DLL(Double Linked List)은 일반적으로 이전 포인터라고 불리는 추가 포인터와 함께
단일 링크 목록에 있는 다음 포인터 및 데이터를 포함한다
요소 추가 순서
예를 들어, 1 2 4 데이터 영역에 3을 추가한다고 하자.
추가할 요소인 3의 다음 요소를 4로 가리키도록 한다.
추가할 요소의 다음 요소인 4의 이전노드를 3의 이전노드를 가리키도록 한다.
추가할 요소의 이전 요소인 2의 다음 노드를 3으로 가리키도록 한다.
Circular Linked List (환형 연결 리스트):
모든 노드가 연결되어 원을 형성하는 연결 목록.
환형 링크 리스트에서, 제1 노드와 마지막 노드는 서로 연결되어 원을 형성.
끝에 NULL이 없다.
SIngly 혹은 Doubly Linked List 에서 Tail 이 Head로 연결되는 연결 리스트 메모리를 아껴쓸 수 있다.
원형 큐 등을 만들때도 사용된다.
Circular singly linked list (환형 단일 연결 리스트):
환형 단일 연결 리스트에서 리스트의 마지막 노드에는 목록의 첫 번째 노드에 대한 포인터가 포함.
시작한 동일한 노드에 도달할 때까지 원형 단일 연결 목록을 통과.
원형 단일 연결 목록에는 시작이나 끝이 없다.
노드의 다음 부분에 null 값이 없다.
Circular Doubly linked list(환형 이중 연결 리스트):
Circular Doubly Linked List는 두 개의 연속된 요소가 이전 포인터와 다음 포인터에 의해
연결되거나 연결되고 마지막 노드가 다음 포인터에 의해 첫 번째 노드를 가리키고
첫 번째 노드가 이전 포인터에 의해 마지막 노드를 가리키는
이중 연결 리스트과 환형 연결 리스트의 속성을 모두 가지고 있다.
https://www.geeksforgeeks.org/data-structures/linked-list/?ref=shm
Linked List Data Structure - GeeksforGeeks
A page for Linked List with a detailed explanation about what is Linked List, types of Linked List, basic operations, and standard problems on Linked List.
www.geeksforgeeks.org
https://www.geeksforgeeks.org/circular-linked-list/
Introduction to Circular Linked List - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
코딩테스트 광탈 방지 A to Z : JavaScript
코딩테스트 광탈 방지 A to Z : JavaScript 자료구조와 알고리즘 기본기를 다지고 문제 풀이 꿀팁까지 한 번에 가져가요! 자료구조와 알고리즘 기초부터 코딩 테스트 대표 유형 문제 풀이까지 “A to Z
school.programmers.co.kr
'자료구조 | 알고리즘' 카테고리의 다른 글
| [자료구조] 큐 (0) | 2023.02.28 |
|---|---|
| [자료구조]스택 (0) | 2023.01.18 |
| [알고리즘]시간 복잡도 (0) | 2023.01.18 |
| 자료구조와 알고리즘의 차이점은? (0) | 2023.01.18 |
| [자료구조]배열(순차리스트) (0) | 2023.01.18 |
