Post
[자료구조]배열, 리스트
배열(Array)
같은 자료형의 데이터를 연속적인 메모리 공간에 저장할 수 있는 자료 구조
같은 자료형만 연속 저장 가능
선언한 배열의 내용물 변경 가능
선언한 배열 길이 변경 불가
c나 c++에서는 기존의 메모리에 있던 값이 그대로 남아 있지만
java에서는 자동으로 배열 내부를 0, false, null로 자동 초기화 되기 때문에 별도의 초기화가 필요하지는 않다.
int[] num = new int[10]; //배열 선언 및 초기화 num[0] = 10; //0부터 시작 num[10] ? //배열 크기 초과 시 Exception 발생
int sum = 0; int[] num = {1, 2, 3, 4, 5}; for (int j : num) { sum += j; } System.out.println(sum);
int[][][] td = new int[10][10][10]; td[0][0][0] = 10;
리스트(List)
복수 데이터를 사용자가 지정한 순서대로 저장하는 자료구조
목록을 구성하는 데이터는 메모리에 연속적으로 위치하지 않아도 됨
목록을 구성하는 데이터의 객체는 메모리 상 여러곳에 존재, 리스트는 각 데이터의 주소 또는 참조 정보만 지님
배열 리스트 (Array List )
내부적으로 배열을 이용해 구현
각 배열의 원소는 데이터 객체에 접근할 수 있는 참조 정보를 보관
인덱스 통해 임의 접근이 빠름
리스트 내부의 배열의 크기가 허용하는 한, 데이터 추가나 마지막 데이터 제거가 용이함
리스트의 크기가 내부 배열을 넘는 경우 더 큰 배열을 다시 생성하기 때문에 성능이 떨어질 수 있음
리스트 중간에 데이터를 삽입 또는 제거하는 경우 내부 배열의 원소들을 밀거나 당겨야 하기 때문에 성능이 떨어질 수 있음
List<String> list = new ArrayList<>(); System.out.println(list.get(0)); //인덱스로 접근 list.set(0,”one”); //수정 list.add(“one”); //추가 list.add(“two”); list.remove(1); //삭제
10000으로 크기 설정하고 10001번 돌려보기
10001번째에 특히 큰 시간이 걸림
10000번째의 추가 이후 10001번째에서 내부에 공간이 없기 때문에 더 큰 새 배열을 생성하고 기존 배열에 있던 참조 정보들을 새 배열로 복사하는 작업이 이루어졌기 때문
연결 리스트 (LInkedList )
임의 접근이 상대적으로 느리지만 리스트의 원소들을 순차적으로 순회하거나 삭제/ 추가할 때 성능이 좋음
리스트 길이의 제약이 적음
중간에 삽입하는 작업이 많을 경우 위처럼 배열리스트인 경우 중간에 데이터 삽입 시 오른쪽을 다 밀어야 한다. 아래 연결리스트에 경우에는 연결이 새로 생성되기 때문에 처리 시 번거로운 부분이 덜 해진다.
연결리스트의 각 노 드 안에는 데이터 참조 링크와, 다음 노드로의 참조 링크를 가지고 있음
=> 각 노드가 메모리 상에 연속적으로 위치할 필요가 없기 때문에 길이의 제약이 적음
=>내부적으로 배열을 사용하지 않기 때문에 리스트 길이 변화 부담이 적음
=>각 리스트의 앞과 뒤에 데이터를 추가하거나 삭제하는 것이 효율적임
연결리스트 클래스 예제
package com.hr.etc.test.test;
//연결리스트 클래스 public class test1 { //연결 리스트의 각 원소를 이루는 노드 클래스 private static class Node { private String data; private Node next;
Node(String data){ this.data = data; this.next = null; } }
//리스트 첫번째 노드 private Node head;
//리스트 마지막 노드, 리스트 끝에 새 노드 추가할 때 사용하기 위함 private Node tail;
//리스트 비었는지 검사 public boolean isEmpty() { return head == null; }
//리스트 끝에 새 데이터 담은 노드 추가 public void addTail(String data){ Node newNode = new Node(data);
if(head == null){ head = newNode; }else{ //주석 부분은 노드가 커지면 작업량이 증가 합니다. /*Node currentNode = head; while (currentNode.next != null){ currentNode = currentNode.next; } currentNode.next = newNode;*/ tail.next = newNode; }
tail = newNode; }
//특정 위치에 있는 노드의 데이터 값 조회 public String get(int targetIndex){ Node currentNode = head; int currentIndex = 0; while (currentNode != null){ if(targetIndex == currentIndex){ return currentNode.data; } currentNode = currentNode.next; currentIndex++; } //연결 노드 위에서 다 조회했는데 원하는 인덱스 값 도달하지 못하는 경우 throw new IndexOutOfBoundsException(String.format(“index %d is out of size”, targetIndex)); }
//리스트 가장 앞 노드 제거 public void removeHead() { if(isEmpty()){ return; } head = head.next; }
// 리스트 맨 마지막 노드 제거 public void removeTail() { if (isEmpty()) { return; }
// 리스트에 노드가 하나만 있을 경우 if (head == tail) { head = null; tail = null; return; }
// 마지막 노드 직전까지 이동 Node currentNode = head; while (currentNode.next != tail) { currentNode = currentNode.next; }
// tail을 이전 노드로 변경하고 마지막 노드 제거 currentNode.next = null; tail = currentNode; }
// 특정 위치(index)에 있는 노드 제거 public void remove(int targetIndex) { if (isEmpty()) { throw new IndexOutOfBoundsException(“List is empty”); }
// 첫 번째 노드(head)를 삭제하는 경우 if (targetIndex == 0) { removeHead(); return; }
Node currentNode = head; Node previousNode = null; int currentIndex = 0;
while (currentNode != null) { if (currentIndex == targetIndex) { // 이전 노드가 다음 노드를 가리키도록 연결 previousNode.next = currentNode.next;
// 만약 삭제한 노드가 tail이었다면 tail 업데이트 if (currentNode == tail) { tail = previousNode; } return; } previousNode = currentNode; currentNode = currentNode.next; currentIndex++; }
throw new IndexOutOfBoundsException(“Index out of range: “ + targetIndex); } }
연결리스트 클래스 사용
package com.hr.etc.test.test;
public class test2 { public static void main(String[] args){ //연결 리스트 생성 test1 list = new test1(); System.out.println(“list.isEmpty() : “ + list.isEmpty());
//추가 list.addTail(“hello”); list.addTail(“world”); list.addTail(“!!”);
//조회 System.out.println(list.get(0)); System.out.println(list.get(1)); System.out.println(list.get(2));
//크기 넘어서는 인덱스 조회 try{ list.get(3); }catch (IndexOutOfBoundsException e){ e.printStackTrace(System.out); }
//첫번째 값 제거 list.removeHead();
//마지막 값 제거 list.removeTail();
list.addTail(“one”); list.addTail(“two”); list.addTail(“three”); list.addTail(“four”);
//index로 제거 list.remove(3); } }
댓글