데이터 구조(Data Structure)란?

- 프로그램에 필요한 데이터를 효율적으로 처리할 수 있도록 데이터 간의 논리적인 관련성을 조직화 하여 표현하는 방법
- 컴퓨터 기억장치에 저장되는 데이터의 형식과 조작에 필요한 연산이 있다.

종류

정적 데이터 구조(Static Data Structure)
- 미리 할당된 크기의 기억장소에 연속적으로 데이터를 저장한 후 조작이나 연산을 하는 것
- 예) Java의 배열(array) int[] score = new int[10];

  ○ 장점

    - 간단한 구조, 기억장소의 사용을 최소화, 데이터 항목에 대한 빠른 검색이 가능하다.

  ○ 단점

    - 미리 기억장소의 연속된 공간을 확보해야한다. (많은 수의 공간을 확보해야한다면 안좋다.)
    - 한번 공간을 할당하면 크기를 변경(축소 또는 증가)이 어렵다.
    - 데이터 항목의 삽입 또는 삭제에 따른 처리 속도의 저하 (모든 데이터를 한칸씩 이동해야 하기 때문에 처리시간이 늘어난다. )

동적 데이터 구조(Dynamic Data Structure)

  - 데이터 항목을 비연속적인 기억장소에 저장하고 링크(link, 레퍼런스)로 연결하여 조작한다.

  - 예) Java의 벡터(Vector)  Vector score = new Vector(10);  java.util.Vector를 import 해야한다.

  ○ 장점

    - 미리 기억장소의 연속된 공간을 확보할 필요가 없다.

    - 프로그램의 실행 도중에 할당된 공간의 크기를 변경시킬수 있다. 

    - 데이터 항목의 삽입과 삭제가 효율적이다.(자료추가시 링크연결만 바꾸면 된다.)

  ○ 단점

    - 프로그램의 처리 방법이 복잡해진다.

    - 링크의 표현에 따른 저장 공간의 비효율성이 증가 (링크도 데이터를 차지한다.)

java.util.Vector 클래스

프로그램의 실행 도중에 길이가 변경될 수 있는 동적 데이터 구조의 리스트

  - 초기 용량(initial capacity)의 설정이 필요하다.

  - 현재 용량을 초과하면 일정한 길이로 용량이 증가(increment capacity)

생성자

  - Vector() : 초기용량이 10으로 주어진 백터 객체를 생성 예) Vector v = new Vector();

  - Vector(int initialCapacity) : 초기용량(int initialCapacity)과 동일한 길이로 증가하는 백터 객체를 생성 예) Vector v = new Vector(100);

  - Vector((int initialCapacity, int capacityIncrement) : 초기용량(int initialCapacity)과 증가분(capacityIncrement)을 갖는 백터 객체 생성 예) Vector v = new Vector(100, 10);

배열과 유사한 메소드

  - void setElementAt(Base_Type newElement, int index)

  - Base_Type elementAt(int index) : Base_Type은 클래스 타입만 가능하며 기본형(int, double 등)은 불가하다. 꼭 넣어야 한다면 클래스타입으로 넣으면 된다.(Wapper클래스)

  - Enumeration elements() : 벡터의 구성원을 열거형(enumeration) 인터페이스로 반환한다.

항목 추가 메소드

  - void addElement(Base_Type newElement) : 현재 있는 값의 끝에 추가한다.

  - void insertElementAt(Base_Type newElement, int index) : 데이터의 특정위치에 값을 삽입할때 사용한다. 뒤의 값은 한칸씩 이동한다.

항목 삭제 메소드

  - void removeElementAt(int index) : 해당 index의 데이터가 삭제되면서 뒤의 값은 index-1 된다.

  - void removeElement(Object theElement) : 특정한 객체를 넣으면 동일한 값을 찾은뒤 제거해준다.

  - void removeAllElements() : 모든 요소를 삭제하여 빈 벡터로 만들어준다.

검색 메소드

  - boolean contains(Object target) : target의 값이 있는지 찾아보고 있으면 true , 없으면  false

  - int indexOf(Object target) : target이 가리키는 객체의 index위치를 출력하여 준다.

  - int lastindexOf(Object target) : 뒤에서부터 뒤져서 제일 먼저 발견되는 target을 돌려준다.

  - Base_Type firstElement() : 첫번째 데이터를 출력

  - Base_Type lastElement() : 마지막 데이터를 출력

메모리 관리 메소드

  - boolean isEmpty() : 현재 벡터가 비어있는지 출력 비어있으면 true 아니면 false

  - int capacity() : 현재 백테의 용량을 반환한다.

  - int size() : 현재 백터에 포함된 항목의 개수를 반환한다.

  - void trimToSize() : 현재 백터의 용량(capacity)을 현재 항목의 크기(size)로 줄여준다.(압축)

기타 메소드

  - Object clone() : 똑같은 벡터로 복사(복제)해준다.

  - boolean equals(Object ) : 다른벡터가 지금 벡터와 같은지 비교해준다.

java.util.Enumeration 인터페이스

  - 백터 또는 해쉬 테이블(hash table)과 같은 선형 데이터 구조에 포함된 항목을 순서대로 처리할 수 있도록 지원하기 위한 인터페이스

메소드

  - boolean hasMoreElements() : 안에 항목이 더 존재하는지 여부를 확인해준다.

  - E nextElements() : 열거형에서 다음에 오는 항목을 반환(E는 항목에 해당하는 객체로 타입에 따라 달라진다.)

예)//v는 벡터형(java.util.vector) 객체일때..

for(Enumeration e = v.elements(); e.hasMoreElements(); ){ 

//e.hasMoreElements()는 Elements가 더있는지 확인

    System.out.println(e.nextElements()); //데이터를 하나씩 꺼내준다.

} //더이상 Elements가 없으면 false가 출력된다.

연결리스트(Linked List)란?

  - 데이터와 링크(또는 참조)로 표현되는 노드(node)로 구성된 동적 데이터 구조이다.

java.util.LinkedList 클래스

  - java에서 표준으로 제공하는 연결리스트 클래스이다.

메소드

  ○ 항목 추가

    - boolean add(E o) / void add(int index, E element)

    - boolean addAll(collection c)

    - void addFirst(E o) / void addLast(E o)

  ○ 항목 수정

    - E set(int index, E element)

  ○ 항목 삭제

    - void clear() / E remove() / E remove(int index)

    - boolean remove(Object o) / E removeFirst() / E removeLast()

  ○ 검색

    - E element() / E get(int index)

    - E getFirst() / E getLast()

    - int indexOf(Object o) / int lastIndexOf(Object o)

    - int size()

노드(Node)의 구현

  - 연결 리스트 구현

public class ListNode {     private String data;     private ListNode link;    public ListNode(){         link = null;         data = null;    }    public ListNode(String newData, ListNode linkValue){         data = newData;         link = linkValue;    }    public void setData(String newData){         data = newData;    }    public String getData(){         return data;    }    public void setLink(ListNode newLink){         link = newLink;    }    public ListNode getLink(){         return link;    }  }

내부 클래스(Inner Class)

  - 클래스 내부에 정의된 클래스(Non-static nested class 라고도 함)

용도

  - 프라이버시의 노출(privacy leak)이 염려되는 데이터 구조 등에서 사용하여 

추상화(abstraction)를 지원

예) StringLinkedList 클래스에서 이용하는 ListNode 클래스

구문법

public class OuterClass{       Declarations_of_OuterClass_Instance_Variables       Definitions_of_OuterClass_Methods       private class InnerClass{             Declarations_of_InnerClass_Instance_Variables             Definitions_of_InnerClass_Methods       }  }