영운's 블로그

이중 연결리스트(Doubly Linked List)의 개념을 정리하고 이를 자바(Java)로 구현하고자 한다. 마지막에는 자바의 Collction Framework에 있는 LinkedList 사용시 반복문 관련 주의할 점을 알아본다. 이중 연결리스트란? 이중 연결리스트는 '단일_연결리스트'와 비교하였을 때 노드가 양방향으로 연결되었다는 차이점을 갖는다. 단일 연결리스트에 있던 head변수와 추가적으로 마지막 노드를 가리키는 tail 변수를 갖는다. tail 변수가 추가됨에 따라 마지막 노드에서 역행적으로 선행 노드로의 접근이 가능해져 접근 연산이 훨씬 빨라진다. 단일 연결 리스트도 Tail 변수를 추가할 수 있지만 리스트의 마지막을 의미할 뿐 단일 연결이기에 리스트의 뒤에서부터 앞으로의 접근은 불가능하기..

연결리스트란? 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 데이터 구조 노드는 데이터 구조를 구성하는 하나의 객체를 의미한다. 포인터는 주소값을 저장하는 것으로 이 포인터가 다른 노드의 주소값을 저장하는 방식으로 노드들이 연결되어 있다. 연결리스트 종류: 단일 연결리스트, 이중 연결리스트, 원형 연결리스트 단일 연결리스트란? 각 노드가 앞에서 뒤로의 연결만을 가진 연결리스트 단일 연결이기에 각 노드의 포인터에는 후행 노드의 주소값이 저장되어 있다. 따라서 앞에서 뒤로의 접근은 가능하지만 뒤에서 앞으로의 접근은 불가하다. 단일 연결 리스트의 구성 하나의 노드는 데이터와 포인터로 이루어져 있다. 단일 연결이기에 포인터는 다음 노드의 주소값만 저장하고 있으며 다시 앞으로 돌아가는 등의 연..

자료구조란? 한정된 메모리 공간 안에서 데이터를 관리(저장, 사용)하기 위한 논리적 구조 자료구조를 왜 알아야 할까? 데이터의 개수가 늘어날 수록 어떠한 자료구조를 사용하는지에 따라 프로그램의 효율성이 크게 달라짐. 따라서 각 자료구조의 장단점을 정확히 파악하여 상황별로 적절한 자료구조를 사용하는 능력을 키워야 한다. 예를 들어 잦은 검색이 필요한 프로그램에서 배열을 사용하는 경우 배열의 맨 앞에서부터 배열의 맨 마지막까지 존재할 수 있기에 평균 시간복잡도는 O(n) 해시 테이블을 사용하는 경우 평균 시간복잡도는 O(1) 하지만 해시테이블은 hash값을 저장할 별도의 공간이 필요하며, 해시 충돌(key에 대응되는 hash가 동일한 경우)을 방지하기 위해 별도의 조치가 필요하고, hash 함수를 사용하는 ..