자료구조6

• 

  01-5)연결 리스트의 확장(1) 를 읽으며 학습한 내용을 정리하는 중 입니다. 지금까지 정리한 연결 리스트는 마지막 노드가 null인 구조로 필요한 기능에 따라 더미 헤드 노드에서 마지막 노드까지 한 방향으로만 데이터를 순회하는 방식이었다. 이는 첫 노드에 접근하는 경우와 마지막 노드로 이동하는 접근성에서 극명한 차이가 발생한다. 만약, 원소 수가 n이고 맨 앞의 삽입 및 삭제를 한다면 상수시간이 발생하지만, 맨 끝에 삽입/삭제를 필요로 한다면 처음부터 끝가지 접근이 필요하여 O(n) 시간이 든다. 이를 해결하기 위해서 연결 리스트에 약간의 구조적 변화를 가미한다. 기존의 연결 리스트는 마지막 노드가 null로 다음 노 드가 삽입되는 형태가 아니라면 가르키는 것이 없다. 여기서 마지막 노드가 첫 번째 노드를 가르키도록 바꾸면 맨 끝의 .. 자료구조/JAVA 2023. 12. 1.

• 

  01-4)배열 리스트와 연결 리스트 를 읽으며 학습한 내용을 정리하는 중 입니다. 배열 리스트와 연결 리스트의 차이를 정리해보자. 배열 리스트는 정적(고정) 크기를 지정하고, 연결 리스트는 원소가 들어오는 점에 맞춰 동적으로 크기를 조절한다는 특징이 있다. 배열 리스트가 고정된 크기를 지정한다는 것은 메모리 상 연속된 공간에 원소를 직접 저장하는 것을 의미한다. 즉 물리적 공간에 연속적으로 데이터를 담는다. 반면, 연결 리스트는 크기를 지정하지 않고 삽입되는 원소에 따라 동적으로 크기를 조절하여 메모리(물리적 공간) 상에 연속적으로 데이터를 담지 않는다는 특징이 있다. ( 비유하자면, 배열 리스트는 원소(데이터)들이 일렬로 줄서서 있는 형태로 직접적인 접근이 가능하다면, 연결 리스트는 각 원소들이 다음 원소의 전화번호를 알아서 전화로 접근.. 자료구조/JAVA 2023. 11. 29.

• 

  01-3)연결 리스트<제네릭> 를 읽으며 학습한 내용을 정리하는 중 입니다. 연결 리스트는 앞선 내용을 살펴봤듯, 데이터 공간을 미리 설정할 필요없이 데이터의 양에 따른 가변적인 추가/삭제에 용이하다. 리스트에 원소가 얼마나 들어올지 예상하기는 쉽지 않으므로, 배열 리스트는 공간을 낭비하지 않는 것이 매우 어렵다. 반면, 연결 리스트는 원소가 추가될 때마다 공간을 할당받아 추가하는 동적 할당 방식을 따르기에 배열의 공간 낭비를 피할 수 있는 자료구조로 자주 쓰인다. 연결 리스트에 숨은 아이디어는 '노드'라고 불리는 요소이다. 노드는 원소를 저장하는 필드(item)와 다음 노드를 가리키는 필드(next)로 구성된다. item필드는 우리가 담을 값을 보유하는 객체이며, 필드 next는 다음 노드를 가리키는 링크(자바의 레퍼런스 c의 포인.. 자료구조/JAVA 2023. 5. 3.

• 

  01-2)배열 리스트<제네릭> 를 읽으며 학습한 내용을 정리하는 중 입니다. 앞서 학습한 배열 리스트를 이번에는 제네릭을 이용하여 구현하는 과정을 작성해보겠습니다. 먼저, 제네릭을 사용할 경우 필요한 인터페이스를 먼저 작성해보자. package list; public interface ListInterFace { public void add(int i, E x); public void append(E x); public E remove(int i ); public boolean removeItem(E x); public E get(int i); public void set(int i, E x); public int indexOf(E x); public int len(); public boolean isEmpty(); public vo.. 자료구조/JAVA 2023. 4. 15.

• 

  01-1)배열 리스트 를 읽으며 학습한 내용을 정리하는 중 입니다. 배열 리스트 객체 구조는 객체 내부에서만 사용될, 즉 필드에서의 배열과 변수가 필요하다. 그리고 다양한 리스트의 기능으로 필요한 메서드(삽입, 추가, 제거..등등)이 리스트 객체를 설계함에 필요하다. 이를 인터페이스로 표현해보자. package list; public interface IntegerListInterface { public void add(int i, Integer x); public void append(Integer x); public Integer remove(int i); public boolean removeItem(Integer x); public Integer get(int i); public void set(int i, Integ.. 자료구조/JAVA 2023. 4. 10.

• 

  01) 리스트 를 읽으며 학습한 내용을 정리하는 중 입니다. 리스트란? 리스트는 여러 데이터를 줄 세워서 보관하는 대표적인 자료구조 중 하나이다. 즉, 자료를 순서대로 한 줄로 저장하는 선형 구조의 자료구조를 리스트라고 부르며, 후에 다룰 Stack, Tree, Queue, Graph등과 같은 다른 자료구조 구현에 활용되는 기초 자료구조이다. 더보기 일반적으로 자료구조의 가장 처음에 배우는 내용으로, 일렬로 나열된 데이터들을 수정, 삭제, 추가등의 기능을 지니고 있다. 1 2 3 4 5 6 흔히 엑셀, 구글 시트와 같은 곳에서 볼 수 있는 한 행의 표처럼, 정보를 일렬로 저장하는 기능이라고 생각하면 좀 더 이해가 쉬울 듯하다. 리스트의 종류 1) 배열 리스트 2) 연결 리스트 둘의 가장 큰 차이점이라면, 배열리스트는 .. 자료구조/JAVA 2023. 4. 9.