[2017.05.15~2017.05.19] 자료구조 2/5

이미지 출처 : http://way2java.com/arrays/one-dimensional-arrays/

순차 자료구조(순차리스트)

ex)배열

*생성시에 크기가 결정된다.(요소(데이터 갯수)의 수)

*Data 중간 삭제, 삽입될 때 -> 요소이동에 따른 오버헤드

=> java.util.ArrayList

내부적으로 배열 구현

add(요소)

set(index, 요소)

추가, 삭제 시 오버헤드 발생

등

Collection(Reference) Vector는 멀티스레딩 환경을 대비해서 만들어졌고 이후에 ArrayList는 단일 쓰레딩 환경으로 대비해서 만들어짐.

Vector

주소: https://docs.oracle.com/javase/8/docs/api/java/util/Vector.html

Vector() Capacity

처음에는 size 10으로 잡았다가 11이 되면 20으로 늘리고 21이 되면 40으로 늘려서 복사한다.

#연결 리스트

이미지 출처 : https://crunchify.com/how-to-iterate-through-linkedlist-instance-in-java/

순차 자료구조의 문제점

• 삽입연산이나 삭제연산 후에 원소들을 이동시키는 추가적인 작업고 시간 소요
• 순차 자료구조는 배열을 이용하여 구현하기 때문에 메모리 사용의 비효율성 문제를 그대로 가짐
• 순차 자료구조에서의 연산 시간, 저장 공간에 대한 문제를 개선한 자료 표현 방법이 필요

연결 자료구조

• 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조
• 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식
• 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현
• 연결하는 방식에 따라 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트

노드

• 연결 자료구조에서 하나의 원소를 표현하기 위한 단위 구조
• 데이터 필드(원소 값 저장, 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성)
• 링크 필드(다음 노드의 주소를 저장, 포인터 변수를 사용하여 주소값을 저장)

리스트 이름 - 연결 리스트의 시작을 가리키는 포인터 변수(연결 리스트의 첫번째 노드를 가리키는 동시에 리스트 전체를 의미)

연결 리스트의 마지막 노드의 링크필드 - 노드의 끝을 표시하기 위해서 null(널) 저장

공백 연결 리스트 - 포인터변수에 null을 저장

이미지 출처 : http://www.java2novice.com/data-structures-in-java/linked-list/singly-linked-list/

단순 연결 리스트

-자유 공간 리스트

풀링에도 사용 가능

p76

삽입, 삭제가 빈번한 경우에는 연결 리스트가 오버헤드가 덜 일어 난다.

https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html

////////////////////////////////////////////////////////////////////////////////////////////////////

p.s

boxing, unboxing

for each

가변 파라미터

제네릭타입

Collection타입의 클래스에 객체를 저장할 때 type 체크 안함

instanceof 타입체크해서 casting

ex) new Vector(); ===> Vector<String> vec = new Vector<String>();

////////////////////////////////////////////////////////////////////////////////////////////////////

이미지 출처 : http://www.geeksforgeeks.org/sorted-insert-for-circular-linked-list/

원형 연결 리스트

-단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트

-삽입하는 노드 new는 리스트의 첫 번째 노드이자 마지막 노드가 되어야 함

이미지 출처 : http://www.java2novice.com/data-structures-in-java/linked-list/doubly-linked-list/

이중 연결 리스트

-양 방향으로 순회할 수 있도록 노드를 연결한 리스트

이미지 출처 : http://howtodoinjava.com/data-structure/java-stack-implementation-array/

//링크드 리스트
import java.io.PrintStream;
import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListTest
{
  public static void main(String[] args)
  {
    LinkedList<string> list = new LinkedList();
    String[] cars = { "아우디", "벤츠", "BMW", "마이바흐", "포르쉐" };
    String[] arrayOfString1;
    int j = (arrayOfString1 = cars).length;
    for (int i = 0; i < j; i++)
    {
      String s = arrayOfString1[i];
      list.add(s);
    }
    Iterator<string> iter = list.iterator();
    while (iter.hasNext()) {
      System.out.println((String)iter.next());
    }
  }
}

#스택

• 접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조
• 스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능
• top의 위치에서만 원소를 삽입하므로 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓인다.
• 후입선출 구조(ex: 연탄 교체할 때)

스택의 연산

삽입 : push

삭제 : pop

스택의 push 알고리즘

• top <- top+1;
• S(top) <- x;

스택의 pop 알고리즘

• return S(top);
• top <- top-1;

순차 자료구조로 구현한 스택의 장점

-순차 자료구조인 1차원 배열을 사용하여 쉽게 구현

순차 자료구조로 구현한 스택의 단점

-물리적으로 크기가 고정된 배열을 사용하므로 스택의 크기 변경 어려움

-순차 자료구조의 단점을 그대로 가지고 있다.

함수의 호출에도 스택을 사용한다.

//스택
public class StackTest
{
  public static void main(String[] args)
  {
    Stack<string> list = new Stack();
    String[] cars = { "아우디", "벤츠", "BMW", "마이바흐", "포르쉐" };
    String[] arrayOfString1;
    int j = (arrayOfString1 = cars).length;
    for (int i = 0; i < j; i++)
    {
      String s = arrayOfString1[i];
      list.push(s);
    }
    while (!list.isEmpty()) {
      System.out.println((String)list.pop() + ", 남은요소" + list.size());
    }
  }
}

//스택을 사용한 괄호 짝({[]}) 확인 소스
import java.io.PrintStream;
import java.util.Scanner;
import java.util.Stack;

public class PairTest
{
  public static void main(String[] args)
  {
    Scanner scanner = new Scanner(System.in);
    System.out.print("입력 : ");
    Stack stack = new Stack();
    String sentence = scanner.next();
    for (int i = 0; i < sentence.length(); i++) {
      switch (sentence.charAt(i))
      {
      case '(': 
      case '[': 
      case '{': 
        stack.push(Character.valueOf(sentence.charAt(i))); break;
      case '}': 
        if (((Character)stack.peek()).charValue() == '{') {
          stack.pop();
        }
        break;
      case ')': 
        if (((Character)stack.peek()).charValue() == '(') {
          stack.pop();
        }
        break;
      case ']': 
        if (((Character)stack.peek()).charValue() == '[') {
          stack.pop();
        }
        break;
      }
    }
    if (stack.empty()) {
      System.out.println("true");
    } else {
      System.out.println("false");
    }
  }
}

/////////////////////////////////////////////////////////////////////////////////////////////////

Set - 중복 객체 저장 안함, 순서 보장 안됨

//HashSet
//TreeSet

import java.io.PrintStream;
import java.util.HashSet;
import java.util.Iterator;
import java.util.TreeSet;

public class SetTest
{
  public static void main(String[] args)
  {
    String[] cars = { "아우디", "벤츠", "BMW", "마이바흐", "포르쉐" };
    HashSet<string> hset = new HashSet();
    TreeSet<string> tset = new TreeSet();
    String[] arrayOfString1;
    int j = (arrayOfString1 = cars).length;
    for (int i = 0; i < j; i++)
    {
      String s = arrayOfString1[i];
      hset.add(s);
      tset.add(s);
    }
    Iterator<string> iter = hset.iterator();
    System.out.print("hashset => ");
    while (iter.hasNext()) {
      System.out.print((String)iter.next() + " ");
    }
    System.out.println();
    
    System.out.print("treeset => ");
    iter = tset.iterator();
    while (iter.hasNext()) {
      System.out.print((String)iter.next() + " ");
    }
  }
}