728x90
자료구조
자료구조(Data Structure)란 무엇인가?
- 프로그램에서 사용할 많은 데이타를 메모리 상에서 관리하는 여러 구현방법들
- 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨
- 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음
- 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해가 중요함
자료구조의 종류
선형 자료구조
- 한 줄로 자료를 관리하는 구조
- 자료들 간의 앞뒤 관계가 1:1의 선형관계
- 배열(Array), 연결리스트(LinkedList), 스택(Stack), 큐(Queue) 등이 있다.
비선형 자료구조
- 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 구조
- 자료들 간의 앞뒤 관계가 1:n, 또는 n:n 의 관계
- 트리(Tree)와 그래프(Graph) 등이 있다.
배열(Array)
배열의 특징
- 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조
- 정해진 크기가 있음
- 요소의 추가와 제거시 다른 요소들의 이동이 필요함
- 배열의 i 번째 요소를 찾는 인덱스 연산이 빠름
- jdk 클래스 : ArrayList, Vector
배열 구현 예제
public class MyArray {
int[] intArr; //int array
int count; //개수
public int ARRAY_SIZE;
public static final int ERROR_NUM = -999999999;
public MyArray()
{
count = 0;
ARRAY_SIZE = 10;
intArr = new int[ARRAY_SIZE];
}
public MyArray(int size)
{
count = 0;
ARRAY_SIZE = size;
intArr = new int[size];
}
public void addElement(int num)
{
if(count >= ARRAY_SIZE){
System.out.println("not enough memory");
return;
}
intArr[count++] = num;
}
public void insertElement(int position, int num)
{
int i;
if(count >= ARRAY_SIZE){ //꽉 찬 경우
System.out.println("not enough memory");
return;
}
if(position < 0 || position > count ){ //index error
System.out.println("insert Error");
return;
}
for( i = count-1; i >= position ; i--){
intArr[i+1] = intArr[i]; // 하나씩 이동
}
intArr[position] = num;
count++;
}
public int removeElement(int position)
{
int ret = ERROR_NUM;
if( isEmpty() ){
System.out.println("There is no element");
return ret;
}
if(position < 0 || position >= count ){ //index error
System.out.println("remove Error");
return ret;
}
ret = intArr[position];
for(int i = position; i<count -1; i++ )
{
intArr[i] = intArr[i+1];
}
count--;
return ret;
}
public int getSize()
{
return count;
}
public boolean isEmpty()
{
if(count == 0){
return true;
}
else return false;
}
public int getElement(int position)
{
if(position < 0 || position > count-1){
System.out.println("검색 위치 오류. 현재 리스트의 개수는 " + count +"개 입니다.");
return ERROR_NUM;
}
return intArr[position];
}
public void printAll()
{
if(count == 0){
System.out.println("출력할 내용이 없습니다.");
return;
}
for(int i=0; i<count; i++){
System.out.println(intArr[i]);
}
}
public void removeAll()
{
for(int i=0; i<count; i++){
intArr[i] = 0;
}
count = 0;
}
}
연결리스트(Linked List)
연결리스트의 특징
- 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조
- 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음
- 자료가 추가 될때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 연결함 (정해진 크기가 없음)
- 연결 리스트의 i 번째 요소를 찾는게 걸리는 시간은 요소의 개수에 비례 : O(n)
- jdk 클래스 : LinkedList
연결리스트 구현 예제
public class MyLinkedList {
private MyListNode head;
int count;
public MyLinkedList()
{
head = null;
count = 0;
}
public MyListNode addElement( String data )
{
MyListNode newNode;
if(head == null){ //맨 처음일때
newNode = new MyListNode(data);
head = newNode;
}
else{
newNode = new MyListNode(data);
MyListNode temp = head;
while(temp.next != null) //맨 뒤로 가서
temp = temp.next;
temp.next = newNode;
}
count++;
return newNode;
}
public MyListNode insertElement(int position, String data )
{
int i;
MyListNode tempNode = head;
MyListNode newNode = new MyListNode(data);
if(position < 0 || position > count ){
System.out.println("추가 할 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return null;
}
if(position == 0){ //맨 앞으로 들어가는 경우
newNode.next = head;
head = newNode;
}
else{
MyListNode preNode = null;
for(i=0; i<position; i++){
preNode = tempNode;
tempNode = tempNode.next;
}
newNode.next = preNode.next;
preNode.next = newNode;
}
count++;
return newNode;
}
public MyListNode removeElement(int position)
{
int i;
MyListNode tempNode = head;
if(position >= count ){
System.out.println("삭제 할 위치 오류입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return null;
}
if(position == 0){ //맨 앞을 삭제하는
head = tempNode.next;
}
else{
MyListNode preNode = null;
for(i=0; i<position; i++){
preNode = tempNode;
tempNode = tempNode.next;
}
preNode.next = tempNode.next;
}
count--;
System.out.println(position + "번째 항목 삭제되었습니다.");
return tempNode;
}
public String getElement(int position)
{
int i;
MyListNode tempNode = head;
if(position >= count ){
System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return new String("error");
}
if(position == 0){ //맨 인 경우
return head.getData();
}
for(i=0; i<position; i++){
tempNode = tempNode.next;
}
return tempNode.getData();
}
public MyListNode getNode(int position)
{
int i;
MyListNode tempNode = head;
if(position >= count ){
System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return null;
}
if(position == 0){ //맨 인 경우
return head;
}
for(i=0; i<position; i++){
tempNode = tempNode.next;
}
return tempNode;
}
public void removeAll()
{
head = null;
count = 0;
}
public int getSize()
{
return count;
}
public void printAll()
{
if(count == 0){
System.out.println("출력할 내용이 없습니다.");
return;
}
MyListNode temp = head;
while(temp != null){
System.out.print(temp.getData());
temp = temp.next;
if(temp!=null){
System.out.print("->");
}
}
System.out.println("");
}
public boolean isEmpty()
{
if(head == null) return true;
else return false;
}
}
스택(Stack)
스택의 특징
- 맨 마지막 위치(top)에서만 자료를 추가,삭제, 꺼내올 수 있음 ( 중간의 자료를 꺼낼 수 없음)
- Last In First Out ( 후입선출 ) 구조
- 가장 최근의 자료를 찾아오거나 게임에서 히스토리를 유지하고 이를 무를때 사용할 수 있음
- 함수의 메모리는 호출 순서에 따른 stack 구조
- jdk 클래스 : Stack
스택 구현 예제
import array.MyArray;
public class MyArrayStack {
int top;
MyArray arrayStack;
public MyArrayStack()
{
top = 0;
arrayStack = new MyArray();
}
public MyArrayStack(int size)
{
arrayStack = new MyArray(size);
}
public void push(int data)
{
if(isFull()){
System.out.println("stack is full");
return;
}
arrayStack.addElement(data);
top++;
}
public int pop()
{
if (top == 0){
System.out.println("stack is empty");
return MyArray.ERROR_NUM;
}
return arrayStack.removeElement(--top);
}
public int peek()
{
if (top == 0){
System.out.println("stack is empty");
return MyArray.ERROR_NUM;
}
return arrayStack.getElement(top-1);
}
public int getSize()
{
return top;
}
public boolean isFull()
{
if(top == arrayStack.ARRAY_SIZE){
return true;
}
else return false;
}
public boolean isEmpty()
{
if (top == 0){
return true;
}
else return false;
}
public void printAll()
{
arrayStack.printAll();
}
}
큐(Queue)
큐의 특징
- 맨 앞(front) 에서 자료를 꺼내거나 삭제하고, 맨 뒤(rear)에서 자료를 추가 함
- Fist In First Out (선입선출) 구조
- 순차적으로 입력된 자료를 순서대로 처리하는데 많이 사용 되는 자료구조
- 콜센터에 들어온 문의 전화, 메세지 큐 등에 활용됨
- jdk 클래스 : ArrayList
큐 구현 예제
import linkedlist.MyListNode;
import linkedlist.MyLinkedList;
interface IQueue{
public void enQueue(String data);
public String deQueue();
public void printAll();
}
public class MyListQueue extends MyLinkedList implements IQueue{
MyListNode front;
MyListNode rear;
public MyListQueue()
{
front = null;
rear = null;
}
public void enQueue(String data)
{
MyListNode newNode;
if(isEmpty()) //처음 항목
{
newNode = addElement(data);
front = newNode;
rear = newNode;
}
else
{
newNode = addElement(data);
rear = newNode;
}
System.out.println(newNode.getData() + " added");
}
public String deQueue()
{
if(isEmpty()){
System.out.println("Queue is Empty");
return null;
}
String data = front.getData();
front = front.next;
if( front == null ){ // 마지막 항목
rear = null;
}
return data;
}
public void printAll()
{
if(isEmpty()){
System.out.println("Queue is Empty");
return;
}
MyListNode temp = front;
while(temp!= null){
System.out.print(temp.getData() + ",");
temp = temp.next;
}
System.out.println();
}
}
'Java' 카테고리의 다른 글
Java - 예외 처리, 로그 (0) | 2022.11.17 |
---|---|
Java - 제네릭, 컬렉션 (0) | 2022.11.17 |
Java - 자바의 유용한 클래스 (0) | 2022.11.17 |
Java - 다형성과 인터페이스 (0) | 2022.11.17 |
Java - 상속 (0) | 2022.11.17 |
댓글