연결리스트
-
[Algorithm] 연결 리스트를 이용한 알고리즘 문제풀이 (Remove Duplicates)카테고리 없음 2020. 8. 12. 22:51
어제 연결 리스트에 대한 포스팅을 올렸으니, 리트코드에서도 연결 리스트와 관련한 문제를 풀어보는 게 좋겠다고 생각했다. 선택한 문제는 다음과 같다. 83. Remove Duplicates from Sorted List Given a sorted linked list, delete all duplicates such that each element appear only once. 정렬된 연결 리스트가 주어졌을 때, 중복되는 값을 가진 요소를 삭제하여 각 요소가 한 번씩만 나오도록 하는 문제다. 예를 들어 연결 리스트의 값이 1-1-2-3으로 주어진다면 이를 1-2-3 으로 수정해주면 된다. 어제 포스팅에서도 잠시 언급했지만, 연결 리스트의 특징은 각 노드는 다음 노드의 주소값을 가지고 있다는 것이다. 그렇..
-
[Data Structure] 연결 리스트와 스킵 리스트카테고리 없음 2020. 8. 11. 19:42
* 연결 리스트(Linked List) 연결 리스트는 일렬로 연결된 데이터를 저장할 때 사용하는 자료구조. 한 노드에는 다음 노드의 주소 정보가 담겨져 있다. 배열과 연결 리스트는 흔히 비교되는 자료구조 형태다. 배열의 경우에는 배열 각 칸들이 물리적으로 한 곳에 모여 있으므로, 크기를 한 번 정하면 늘리거나 줄일 수 없다. 반면, 연결 리스트의 경우 데이터를 중간에 삽입을 하는 것이 용이하다. 가령, A노드와 C 노드 사이에 B 노드를 추가하려는 경우, B 노드의 다음 주소를 C노드로 연결하고, A노드의 다음 주소를 B노드로 연결하면 된다. (관련 알고리즘 문제풀이) 연결 리스트는 주소를 일일이 찾아다녀야 하기 때문에 배열보다 검색 속도가 느릴 수 있다. 반면 위에서 본 것 처럼 데이터를 중간에 추가하..