본문 바로가기
국비 교육

2020.8.17일자 수업 : ArrayList, LinkedList

은근이506 2020. 8. 17. 20:10

실습 - ArrayList 구현하기

git/ bitcamp-20200713/ bitcamp-java-basic/ src/ main/ java com.eomcs.corelib.ex04.MyLinkedList14~21.java

4단계 : 인스턴스를 생성할 때 배열의 초기 크기를 설정할 수 있도록 생성자와 초기 크기를 지정하지 않는 기본 생성자를 구현한다.를 구현한다. 배열 크기를 지정할 때 기본 크기보다는 큰 값이 되도록 생성자를 구현한다. 초기 크기를 1로 할 경우에는 크기가 안늘려지기 때문이다. 배열의 기본 크기는 직접 숫자로 지정하지 말고 상수를 사용하여 지정한다.

package com.eomcs.algorithm.data_structure.array;

public class MyArrayList {
  private Object[] elementData;
  // 기본 배열 길이 상수 추가
  private static final int DEFAULT_LENGTH = 5;
  private int size;
  
  // 기본 생성자 추가
  public MyArrayList() {
    elementData = new Object[DEFAULT_LENGTH];
  }
  
  // 배열 길이를 파라미터로 하는 생성자 추가
  public MyArrayList(int length) {
    if (length < 5) {
      elementData = new Object[DEFAULT_LENGTH];
    } else {
    elementData = new Object[length];
    }
  }

  public boolean add(Object e) {
    if (size == elementData.length) {
      grow();
    }
    elementData[size++] = e;
    return true;
  }

  private void grow() {
    System.out.println("오호라! 배열을 늘리자.");
    Object[] newArray = new Object[elementData.length + (elementData.length >> 1)];
    for (int i = 0; i < elementData.length; i++) {
      newArray[i] = elementData[i];
    }
    elementData = newArray;
  }


  public void add(int index, Object element) {
    if (size == elementData.length) {
      grow();
    }
    if (index < 0 || index > size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    for (int i = size; i > index ; i--) {
      elementData[i] = elementData[i - 1];
    }
    elementData[index] = element;
    size++;
  }

  public Object get(int index) {
    if (index < 0 || index >= size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    return elementData[index];
  }

  public Object set(int index, Object element) {
    if (index < 0 || index >= size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    Object old = elementData[index];
    elementData[index] = element;
    return old;
  }

  public Object remove(int index) {
    if (index < 0 || index >= size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    Object old = elementData[index];

    for (int i = index; i < size - 1; i++) {
      elementData[i] = elementData[i + 1];
    }

    size--;
    elementData[size] = null;
    return old;
  }

  public int size() {
    return this.size;
  }
}

5단계 : 배열의 크기를 늘릴 때 자바에서 제공하는 Arrays를 사용하여 처리한다. 배열을 다루는 도구 Arrays 클래스에 copyOf 메서드는 복사하고자하는 배열과 그것보다 더 큰 크기를 파라미터로 주면 원본 값을 복사하여 더 큰 크기의 새 배열에 넣어서 만들어 준다.

package com.eomcs.algorithm.data_structure.array;

import java.util.Arrays;

public class MyArrayList {
  private Object[] elementData;
  private static final int DEFAULT_LENGTH = 5;
  private int size;
  
  public MyArrayList() {
    elementData = new Object[DEFAULT_LENGTH];
  }
  
  public MyArrayList(int length) {
    if (length < 5) {
      elementData = new Object[DEFAULT_LENGTH];
    } else {
      elementData = new Object[length];
    }
  }

  public boolean add(Object e) {
    if (size == elementData.length) {
      grow();
    }
    elementData[size++] = e;
    return true;
  }

  private void grow() {
    System.out.println("오호라! 배열을 늘리자.");
    // Arrays 클래스의 copyOf() 메서드를 통해서 더 큰 길이의 배열을 만들고 기존 배열을 복사해서 넣는다.
    Object[] newArray = Arrays.copyOf(elementData, 
        elementData.length + (elementData.length >> 1));
    elementData = newArray;
  }


  public void add(int index, Object element) {
    if (size == elementData.length) {
      grow();
    }
    if (index < 0 || index > size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    for (int i = size; i > index ; i--) {
      elementData[i] = elementData[i - 1];
    }
    elementData[index] = element;
    size++;
  }

  public Object get(int index) {
    if (index < 0 || index >= size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    return elementData[index];
  }

  public Object set(int index, Object element) {
    if (index < 0 || index >= size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    Object old = elementData[index];
    elementData[index] = element;
    return old;
  }

  public Object remove(int index) {
    if (index < 0 || index >= size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    Object old = elementData[index];

    for (int i = index; i < size - 1; i++) {
      elementData[i] = elementData[i + 1];
    }

    size--;
    elementData[size] = null;
    return old;
  }

  public int size() {
    return this.size;
  }
}

6단계 : 배열을 특정 항목을 삭제, 삽입할 때 배열 복사 기능을 이용하여 처리한다.

System.arraycopy(복사 대상, 복사할 항목의 시작 인덱스, 목적지, 목사 목적지 인덱스, 복사할 인덱스 길이)

package com.eomcs.algorithm.data_structure.array;

import java.util.Arrays;

public class MyArrayList {
  private Object[] elementData;
  private static final int DEFAULT_LENGTH = 5;
  private int size;
  
  public MyArrayList() {
    elementData = new Object[DEFAULT_LENGTH];
  }
  
  public MyArrayList(int length) {
    if (length < 5) {
      elementData = new Object[DEFAULT_LENGTH];
    } else {
      elementData = new Object[length];
    }
  }

  public boolean add(Object e) {
    if (size == elementData.length) {
      grow();
    }
    elementData[size++] = e;
    return true;
  }

  private void grow() {
    System.out.println("오호라! 배열을 늘리자.");
    Object[] newArray = Arrays.copyOf(elementData, 
        elementData.length + (elementData.length >> 1));
    elementData = newArray;
  }


  public void add(int index, Object element) {
    if (size == elementData.length) {
      grow();
    }
    if (index < 0 || index > size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    // arraycopy를 사용해서 index + 1부터 배열을 복사하여 같은 배열의 index부터 놓는다.
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    
    elementData[index] = element;
    size++;
  }

  public Object get(int index) {
    if (index < 0 || index >= size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    return elementData[index];
  }

  public Object set(int index, Object element) {
    if (index < 0 || index >= size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    Object old = elementData[index];
    elementData[index] = element;
    return old;
  }

  public Object remove(int index) {
    if (index < 0 || index >= size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    Object old = elementData[index];
    // arraycopy를 사용해서 index + 1부터 배열을 복사하여 같은 배열의 index부터 놓는다.
    System.arraycopy(elementData, index + 1, elementData, index, size - (index + 1));
    size--;
    elementData[size] = null;
    // 쓰지 않는 인스턴스의 주소를 제거하여
    // 가비지 될 수 있게 한다.

    return old;
  }

  public int size() {
    return this.size;
  }
}

7단계 : ArrayList에 보관되어있는 인스턴스 목록을 배열로 리턴하는 toArray() 메서드를 추가한다. toArray()에서 배열을 복사할 때 Arrays.copyOf() 메서드를 활용해보자.

package com.eomcs.algorithm.data_structure.array;

import java.util.Arrays;

public class MyArrayList {
  private Object[] elementData;
  private static final int DEFAULT_LENGTH = 5;
  private int size;
  
  public MyArrayList() {
    elementData = new Object[DEFAULT_LENGTH];
  }
  
  public MyArrayList(int length) {
    if (length < 5) {
      elementData = new Object[DEFAULT_LENGTH];
    } else {
      elementData = new Object[length];
    }
  }

  public boolean add(Object e) {
    if (size == elementData.length) {
      grow();
    }
    elementData[size++] = e;
    return true;
  }

  private void grow() {
    System.out.println("오호라! 배열을 늘리자.");
    Object[] newArray = Arrays.copyOf(elementData, 
        elementData.length + (elementData.length >> 1));
    elementData = newArray;
 
  }


  public void add(int index, Object element) {
    if (size == elementData.length) {
      grow();
    }
    if (index < 0 || index > size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    
    elementData[index] = element;
    size++;
  }

  public Object get(int index) {
    if (index < 0 || index >= size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    return elementData[index];
  }

  public Object set(int index, Object element) {
    if (index < 0 || index >= size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    Object old = elementData[index];
    elementData[index] = element;
    return old;
  }

  public Object remove(int index) {
    if (index < 0 || index >= size) {
      throw new ArrayIndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    Object old = elementData[index];

    System.arraycopy(elementData, index + 1, elementData, index, size - (index + 1));
    size--;
    elementData[size] = null;
    return old;
  }

  public int size() {
    return this.size;
  }
  // copyOf() 메서드를 이용하여 해당 목록의 값들을 size만큼의 길이의 배열에 복사하는 메서드를 만든다.
  public Object[] toArray() {
    Object[] arr = Arrays.copyOf(this.elementData, this.size);
    return arr;
  }
}

ArrayList

git/ bitcamp-20200713/ bitcamp-java-basic/ src/ main/ java com.eomcs.corelib.ex03.Exam0210~0330.java

contains(Object)

이 메서드는 파라미터로 주는 인스턴스와 같은 객체가 있는 지 알아낸다. 단 인스턴스 주소를 비교하는 것이 아니라, equals()의 결과가 true인지를 확인한다. String 클래스의 경우에는 equals()를 오버라이딩 했으므로 서로 다른 객체라도 같은 값이면 같은 객체로 간주한다.

이것은 레퍼런스를 Object 클래스 타입으로 해도 상관없다. 메서드는 인스턴스 클래스 타입에서부터 찾아올라가기 때문이다.

중요한 것은 새로운 클래스 타입을 정의해놓고 equals()를 오버라이딩하지 않으면, contains()를 사용해서 같은 값을 가진 객체를 알려고 해도 원하는 것이 리턴되지 않는다는 것이다. 

package com.eomcs.corelib.ex03;

import java.util.ArrayList;

public class Exam0220 {

  // equals()를 오버라이딩 하지 않았다.
  static class Member {
    String name;
    int age;

    public Member(String name, int age) {
      this.name = name;
      this.age = age;
    }

    @Override
    public String toString() {
      return String.format("[%s,%d]", this.name, this.age);
    }
  }

  public static void main(String[] args) {
    Member s1 = new Member("홍길동", 20);
    Member s2 = new Member("임꺽정", 30);
    Member s3 = new Member("유관순", 16);
    Member s4 = new Member("임꺽정", 30);

    ArrayList list = new ArrayList();
    list.add(s1);
    list.add(s2);
    list.add(s3);
    print(list);
    
    // [홍길동,20], [임꺽정,30], [유관순,16], 

    System.out.println(list.contains(s4)); // false
  }

  static void print(ArrayList list) {
    for (int i = 0; i < list.size(); i++) {
      System.out.print(list.get(i) + ", ");
    }
    System.out.println();
  }
}

따라서 이와 같은 결과를 얻으려면equals()를 오버라이딩이 필수이다.

package com.eomcs.corelib.ex03;

import java.util.ArrayList;

public class Exam0230 {
  static class Member {
    String name;
    int age;

    public Member(String name, int age) {
      this.name = name;
      this.age = age;
    }

    @Override
    public String toString() {
      return String.format("[%s,%d]", this.name, this.age);
    }

    @Override
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (obj == null)
        return false;
      if (getClass() != obj.getClass())
        return false;
      Member other = (Member) obj;
      if (age != other.age)
        return false;
      if (name == null) {
        if (other.name != null)
          return false;
      } else if (!name.equals(other.name))
        return false;
      return true;
    }
  }

  public static void main(String[] args) {
    Member s1 = new Member("홍길동", 20);
    Member s2 = new Member("임꺽정", 30);
    Member s3 = new Member("유관순", 16);
    Member s4 = new Member("임꺽정", 30);

    ArrayList list = new ArrayList();
    list.add(s1);
    list.add(s2);
    list.add(s3);
    print(list);

    System.out.println(list.contains(s4)); // true
  }

  static void print(ArrayList list) {
    for (int i = 0; i < list.size(); i++) {
      System.out.print(list.get(i) + ", ");
    }
    System.out.println();
  }
}

 

index0f(Object)

이 메서드는 파라미터로 주는 인스턴스와 같은 객체가 있는 인덱스를 리턴하며 객체를 찾지 못하면 -1을 리턴한다. contains()와 마찬가지로 equals()를 오버라이딩하지 않으면 원하는 값을 리턴받을 수 없다. 딷라서 같은 값을 가진 객체가 어떤 인덱스에 있는 지 알아내고 싶다면 equals()의 오버라이딩은 필수이다.

 

LinkedList

git/ bitcamp-20200713/ bitcamp-java-basic/ src/ main/ java com.eomcs.corelib.ex04.Exam0110.java

ArrayList는 외부적으로 봤을 때 배열 크기가 가변적이고 순서(인덱스)가 있다는 점에서 기능은 비슷하지만 내부적인 원리가 다르다.

내부적인 차이점

  • ArrayList는 고정 크기를 가지는 배열을 사용하는 것이 기본이다. 따라서 크기를 초과하면 더 큰 배열을 새로 만듦으로써 크기 제한을 극복한다.
  • LinkedList는 배열을 사용하지 않고, 각 항목에 대응하는 인스턴스들을 만들고 이 데이터들을 직렬적으로 연결하는 방식으로 배열의 형태를 만든다. 따라서 하나의 요소를 추가할 때마다 정확히 하나씩 메모리가 발생한다. 

메모리 효율성

  • ArrayList는 실제 사이즈보다 더 큰 배열을 만들기 때문에 메모리 낭비가 심하다. 또한 크기가 초과되어 새 배열을 만들면 기존 배열은 가비지가 되므로 가비지도 과다 생산된다.
  • LinkedList는 비록 한 값에 인스턴스 하나가 생성되긴 하지만 값들의 수를 넘어서 메모리를 만들지 않기 때문에 메모리 낭비가 적고 가비지를 덜 생산한다.

속도

  • ArrayList는 특정 항목를 조회할 때 인덱스를 이용하여 검색하기 때문에 검색 속도가 빠르다. 그러나 요소를 삭제하거나 삽입할 때 그 뒤의 항목을 모두 한칸씩 이동해야하기 때문에 속도가 느리다.
  • LinkedList는 다만 특정 항목을 찾는 경우에는 첫 항목부터 추적해나가므로 속도가 느리다. 그러나 삭제할 때 이전 항목과 다음 항목을 바로 연결하면 되기 때문에 속도가 빠르며, 삽입할 때에도 현재 항목과 새 항목을 연결하면 되기 때문에 속도가 빠르다. 비록 삭제나 삽입 과정에서도 해당 인덱스를 첫 항목부터 찾아나가야하는 것은 같지만, ArrayList처럼 뒤에 있는 모든 항목을 하나씩 이동하는 것보다는 빠를 것이다.

 

LinkedList의 원리를 한번 살펴보자

LinkedList는 배열을 사용하지 않고, 요소를 새로 넣을 때마다 하나의 인스턴스를 생성한다. 그리고 이전 인덱스에 해당하는 인스턴스에 새로 추가된 인스턴스 주소를 저장한다. 이처럼 마지막 인스턴스의 주소를 참조할 때까지, 모든 인스턴스는 다음 항목의 인스턴스를 참조하는 방식으로 메모리들이 연결이 된다.

LinkedList에서 생성되는 각각의 인스턴스는 node라고 불린다.

 

중간에 항목을 삽입하는 경우

삽입하려는 인덱스의 바로 앞에 위치한 노드가 새롭게 생성된 인스턴스의 주소를 가리키게 하고 새롭게 생성된 인스턴스는 해당 인덱스에 원래 있던 인스턴스 주소를 가리키게 한다. 

 

중간에 항목을 삭제하는 경우

삭제하려는 인덱스의 바로 앞에 위치한 노드가 지우려는 인스턴스 뒤의 인스턴스 주소를 가리키게 하고, 해당 인스턴스의 주소 값을 null로 해준다.

 

삽입과 삭제 과정은 처음 메모리부터 추적해야하는 대신 교체하는 것이 해당 메모리와 전 메모리에 저장된 주소 값 뿐이므로 속도가 빠르다. 

 

실습 - LinkedList 구현하기

git/ bitcamp-20200713/ bitcamp-java-basic/ src/ main/ java com.eomcs.corelib.ex04.MyLinkedList01~12.java

1단계 : Node 클래스를 정의하고, MyLinkedList 클래스의 필드로는 first 노드와 last 노드의 주소를 넣을 변수와 목록 크기를 보관하는 변수를 지정한다. 노드 클래스는 모두가 함께 공유할 클래스 설계도이므로 static 이 되어야하고 value값을 바로 초기화시킬수 있도록 생성자를 만들어준다.

package com.eomcs.corelib.ex04;

public class MyLinkedList {
  
  Node first;
  Node last;
  int size;

  public static class Node {
    Object value;
    Node next;
    
    Node(Object value) {
      this.value = value;
    }
  }
}

2단계 : 값을 가장 뒤에 추가하는 add(Object) 메서드를 선언한다. 처음으로 호출하는 경우면 first, last가 해당 노드를 가리키게 하고, 이외에는 기존 last 객체의 next 주소 값을 해당 노드로 한 다음에 last를 해당 노드를 가리키게끔 변경한다.

package com.eomcs.corelib.ex04;

public class MyLinkedList {
  
  Node first;
  Node last;
  int size = 0;

  public class Node {
    Object value;
    Node next;
    
    private Node(Object value) {
      this.value = value;
    }
  }
  add() 메서드 추가
  public boolean add(Object value) {
    Node node = new Node(value);
    if (size == 0) {
      first = node;

    } else {
      last.next = node;
    }
    last = node;
    size++;
    return true;
  }
}

 

3단계 : 파라미터에 해당하는 인덱스의 값을 조회하는 get(int) 메서드를 추가한다. 유효 인덱스 범위를 설정하고, 그 밖의 인덱스를 설정하면 에러를 띄운다. 커서라는 참조변수가 해당 인덱스를 가리키게 하고 이를 통해 값을 조회한다.

package com.eomcs.corelib.ex04;

public class MyLinkedList {
  
  Node first;
  Node last;
  int size = 0;

  public class Node {
    Object value;
    Node next;
    
    private Node(Object value) {
      this.value = value;
    }
  }
  
  public boolean add(Object value) {
    Node node = new Node(value);
    if (size == 0) {
      first = node;

    } else {
      last.next = node;
    }
    last = node;
    size++;
    return true;
  }
  
  // get() 메서드 추가
  public Object get(int index) { 
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    Node cursor = this.first;
    for (int i = 0; i < index; i++) {
      cursor = cursor.next;
    }
    return cursor.value;
  }
}

4단계 : 특정 인덱스 위치에 값을 삽입하는 add(int, Object) 메서드를 추가한다. 유효 인덱스 범위를 설정하고, 그 밖의 인덱스를 설정하면 에러를 띄운다. 커서라는 참조 변수로 해당 인덱스 전의 인덱스를 찾는다. 삽입하려는 인스턴스의 next가 원래 인덱스에 있던 인스턴스를 가리키게 하고, 바로 앞 항목의 next는 삽입하려는 인스턴스를 가리키게 한다. 쉽게 말하면 연결고리에 삽입되는 인스턴스가 자연스럽게 낄 수 있도록 해주면 된다. 만약 해당 인덱스가 0이라면 커서가 해당 인덱스 전 인덱스를 가리키지 못하기 때문에 따로 조건문을 달아서 해당 메모리의 next 변수가 기존 첫번째 메모리를 가리키게 한 후 first가 해당 메모리를 가리키도록 변경해줘야한다. 만약 해당 인덱스가 size와 같은 값이라면, last를 새로 삽입한 인덱스로 변경해주지 않으면 배열이 꼬이게 되어 사이즈와 실제 배열크기가 안 맞게 된다.

package com.eomcs.corelib.ex04;

public class MyLinkedList {
  
  Node first;
  Node last;
  int size = 0;

  public class Node {
    Object value;
    Node next;
    
    private Node(Object value) {
      this.value = value;
    }
  }
  
  public boolean add(Object value) {
    Node node = new Node(value);
    if (size == 0) {
      first = node;

    } else {
      last.next = node;
    }
    last = node;
    size++;
    return true;
  }
  
  public Object get(int index) { 
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    Node cursor = this.first;
    for (int i = 0; i < index; i++) {
      cursor = cursor.next;
    }
    return cursor.value;
  }
  // add(int, Object) 추가
  public void add(int index, Object value) {
    if (index < 0 || index > size) {
      throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    size++;
    Node node = new Node(value);
    // 첫 항목으로 추가할 경우
    if (index == 0) {
      node.next = first;
      first = node;
      return ;
    } 
    
    Node cursor = this.first;
    for (int i = 0; i < index -1; i++) {
      cursor = cursor.next;
    }
    node.next = cursor.next;
    cursor.next = node;
    // 마지막에 추가되는 경우
    if (node.next == null) {
      last = node;
    }
  }
}

 

5단계 : 특정 인덱스의 있는 인스턴스를 삭제하는 remove(int)를 추가한다. 유효 범위의 인덱스를 지정해주고, 삭제하려는 항목 바로 앞의 항목의 next는 삭제하려는 항목 다음의 항목을 가리키도록 하기만 하면 된다. 그후 삭제되는 인스턴스는 온전히 가비지가 될 수 있도록 남아있는 모든 연결고리를 끊어준다. 쉽게 말하면, 삭제하는 인스턴스를 연결고리에서 빼서 구멍을 자연스럽게 이어주는 것이다. 가장 처음 항목을 삭제하는 경우에는 그것보다 더 전 인덱스가 없기 때문에 조건문을 따로 달아서 직접 first를 기존의 두번째 항목으로 지정해주고 남은 연결고리를 끊는다. 마지막 항목을 삭제하는 경우에는 배열이 꼬이지 않도록 last를 다시 지정해주고 남은 연결고리를 끊어준다.

package com.eomcs.corelib.ex04;

public class MyLinkedList {
  
  Node first;
  Node last;
  int size = 0;

  public class Node {
    Object value;
    Node next;
    
    private Node(Object value) {
      this.value = value;
    }
  }
  
  public boolean add(Object value) {
    Node node = new Node(value);
    if (size == 0) {
      first = node;

    } else {
      last.next = node;
    }
    last = node;
    size++;
    return true;
  }
  
  public Object get(int index) { 
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    Node cursor = this.first;
    for (int i = 0; i < index; i++) {
      cursor = cursor.next;
    }
    return cursor.value;
  }
  
  public void add(int index, Object value) {
    if (index < 0 || index > size) {
      throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    size++;
    Node node = new Node(value);
    
    if (index == 0) {
      node.next = first;
      first = node;
      return ;
    } 
    
    Node cursor = this.first;
    for (int i = 0; i < index -1; i++) {
      cursor = cursor.next;
    }
    node.next = cursor.next;
    cursor.next = node;
    
    if (node.next == null) {
      last = node;
    }
  }
  // remove(int) 메서드 추가
  public Object remove(int index) {
  // 유효범위 지정
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    
    size--;
    // 첫 항목을 삭제하는 경우
    if (index == 0) {
      Node old = first;
      first = old.next;
      old.next = null;
      return old.value;
    }
    
    Node cursor = this.first;
    for (int i = 0; i < index -1; i++) {
      cursor = cursor.next;
    }
    
    Node old = cursor.next;
    cursor.next = old.next;
    old.next = null;
    // 끝 항목을 삭제하는 경우
    if (cursor.next == null) {
      last = cursor; 
    }
    
    return old.value;
  }
}

6단계 : 특정 인덱스의 값을 바꾸는 set(int, Object)를 추가하고 목록 데이터를 새 배열에 담아 리턴하는 toArray() 메서드를 정의한다. 

package com.eomcs.corelib.ex04;

public class MyLinkedList {
  
  Node first;
  Node last;
  int size = 0;

  public class Node {
    Object value;
    Node next;
    
    private Node(Object value) {
      this.value = value;
    }
  }
  
  public boolean add(Object value) {
    Node node = new Node(value);
    if (size == 0) {
      first = node;

    } else {
      last.next = node;
    }
    last = node;
    size++;
    return true;
  }
  
  public Object get(int index) { 
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    Node cursor = this.first;
    for (int i = 0; i < index; i++) {
      cursor = cursor.next;
    }
    return cursor.value;
  }
  
  public void add(int index, Object value) {
    if (index < 0 || index > size) {
      throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    size++;
    Node node = new Node(value);
    
    if (index == 0) {
      node.next = first;
      first = node;
      return ;
    } 
    
    Node cursor = this.first;
    for (int i = 0; i < index -1; i++) {
      cursor = cursor.next;
    }
    node.next = cursor.next;
    cursor.next = node;
    
    if (node.next == null) {
      last = node;
    }
  }
  
  public Object remove(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    
    size--;
    if (index == 0) {
      Node old = first;
      first = old.next;
      old.next = null;
      return old.value;
    }
    
    Node cursor = this.first;
    for (int i = 0; i < index -1; i++) {
      cursor = cursor.next;
    }
    
    Node old = cursor.next;
    cursor.next = old.next;
    old.next = null;
    
    if (cursor.next == null) {
      last = cursor; 
    }
    
    return old.value;
  }
  // set(int, Object) 메서드 추가
  public Object set(int index, Object value) {
  // 인데스 유효범위 지정
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
    }
    Node cursor = this.first;
    for (int i = 0; i < index; i++) {
      cursor = cursor.next;
    }
    Object old = cursor.value;
    cursor.value = value;
    return old;
  }
  // toArray() 메서드 추가
  public Object[] toArray() {
    Object[] arr = new Object[size];
    Node cursor = this.first;
    int count = 0;
    while (cursor != null) {
      arr[count++] = cursor.value;
      cursor = cursor.next;
    }
    return arr;
  }
}

 

면접예상 질문 참고 eomcs.docs 

'국비 교육' 카테고리의 다른 글

2020.8.19일자 수업 : 미니프로젝트  (0) 2020.08.19
2020.8.14일자 수업 : String, Wrapper, ArrayList 구현 실습  (0) 2020.08.15
2020.8.12일자 수업 : 오버로딩, 오버라이딩, 캡슐화  (0) 2020.08.12

'국비 교육' Related Articles

티스토리툴바