본문 바로가기

단일연결리스트2

[자료구조] 단일연결리스트 reverse 메서드 구현 (java) 단일연결리스트의 reverse 메서드를 구현해봅시다. 단일연결리스트의 객체는 head 정보, 그리고 노드는 다음 노드 정보만 가지고 있는 가장 단순한 형태의 단일연결리스트입니다. 코드로 표현하면 다음과 같습니다. public class SinglyLinkedList { Node head; static class Node { int data; Node next; } } 코드를 복잡하게 만들지 않기 위해서 toString()이나 add() 메서드는 이미 구현되어 있다고 가정하겠습니다. public class UnitTest { public static void main(String[] args) { SinglyLinkedList list = new SinglyLinkedList(); list.addLast(.. 2020. 11. 13.
[자료구조] 파이썬으로 단일연결리스트 구현하기 단일연결리스트 동적 배열의 단점 동적 배열은 연속된 메모리 공간에 값을 할당한다. 파이썬의 리스트는 값을 직접 저장하지 않고 해당하는 객체의 주소를 저장하는 레퍼런스 배열이기 때문에 다른 언어의 배열과는 약간 다르다. 동적 배열은 먼저 크기를 할당해 메모리 공간을 미리 확보해놓고 이후에 값을 저장하기 때문에 대부분의 경우 저장하는 요소의 수가 배열의 길이보다 작다. append 연산은 분할 분석 방식으로는 O(1) 의 시간복잡도를 가지지만 실제로는 배열이 가득 찼을 때 resize 연산을 하면서 O(n) 의 시간복잡도를 가진다. 즉 특정 시점(배열이 가득 찼을 때)에 연산 속도가 갑자기 느려진다. 이는 실시간 시스템에서는 문제를 유발할 수 있다. 동적 배열의 단점을 정리하면 아래와 같다. 동적 배열의 길.. 2020. 11. 8.