[자료구조] 리스트-1

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.: https://github.com/ejImDev/data_structure_study.git

List

일련의 동일한 타입의 항목들
1차원 배열, 단순연결리스트, 이중연결리스트, 환형연결리스트 등

배열

동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 각 항목이 하나의 원소에 저장되는 기본적 자료구조
특정 원소에 접근할 때 배열의 인덱스를 이용하여 O(1) 시간에 접근 가능
새 항목이 배열 중간에 삽입되거나 중간에 있는 항목을 삭제하면, 뒤 항목을 한칸씩 앞,뒤로 이동시켜야 하므로 연산은 항상 O(1) 시간에 수행할 수 없음

장점
- 구현이 쉽다
- 참조를 위한 추가 메모리가 필요없다
- 연속적이라 메모리 관리가 편하다
- 인덱스를 통해 빠른 접근이 가능하다
단점
- 배열의 크기를 변경할 수 없다
- 크기를 선언하더라도 사용하지 않는 공간이 있을 수 있어 메모리 낭비가 발생한다

배열로 구현한 리스트 만들기 (A)

ArrList

public class ArrList <E> {
  private E a[];
  private int size;
  public ArrList() {
      a = (E[]) new Object[1];
      size = 0;
  }
}

peek 메소드 코드 (k번째 항목을 리턴)

public E peek(int k) {
  if(size == 0) {
      throw new NoSuchElementException();
  }
  return a[k];
}

insertLast (마지막에 새 항목 추가)

public void insertLast (E newItem) {
  if(size == a.length) {
      resize(2*a.length); // 배열에 빈 공간이 없으면 배열 크기 2배로 확장
  }
  a[size++] = newItem;
}

insert (새 항목을 지정한 위치에 추가)

public void insert (E newItem, int k) {
  if(size == a.length) {
      resize(2*a.length);
  }
  for(int i==size-1; i>=k; i--){
      a[i+1] = a[i];
  }
  a[k] = newItem;
  size++;
}

resize (배열크기 재조절)

private void resize(int newSize) {
  Object[] t = new Object[newsize];
  for(int i=0; i<size; i++){
      t[i] = a[i];
  }
  a = (E[]) t;
}

delete(배열항목 삭제)

private E delete(int k) {
  if(isEmpty()) {
      throw new NoSuchElementException();
  }
  for(int i=k; i<size; i++) {
      a[i] = a[i+1];
  }
  size--;
  if(size>0 && size==a.length/4){
      resize(a.length/2);
  }
  return item;
}

A 정리

peek 메소드는 배열 원소에 직접 접근하므로 O(1)시간 소요
삽입이나 삭제는 각 항목의 위치를 한칸씩 이동이 필요하므로 최악의 경우 O(N)시간 소요
새 항목을 가장 뒤에 삽입하는 경우 O(1)시간 소요
배열의 크기를 확대 또는 축소 시키는 것도 최악경우 O(N)시간 소요
상각분석에 따르면 삽입이나 삭제의 평균 수행시간은 O(1)시간 소요

단순연결리스트로 구현한 리스트 만들기 (B)

동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조
노드를 저장하고, 노드는 레퍼런스를 이용하여 다음 노드를 가리켜 노드를 한줄로 연결
삽입이나 삭제시 항목들의 이동이 필요 없음
생성시 크기를 결정하는 방식이 아니므로 빈공간이 존재하지 않음
항목을 탐색하려면 항상 첫 노드부터 차례로 방문하는 순차탐색을 해야 함

노드의 형식

public class Node <E> {
 private E item;
 private Node<E> next;
 public Node(E newItem, Node<E> node){
     item = newItem;
     next = node;
 }

 public E getItem() { return item; }
 public Node<E> getNext { return next; }
 public void setItem(E newItem) { item = newItem; }
 public void setNext(Node<E> newNext) { next = new Next; }
}

코드 예시

리스트를 단순연결리스트로 구현한 SList 클래스

public class SList <E> {
 protected Node head; // 첫 노드
 private int size; // 사이즈
 public SList(){
   head = null;
   size = 0;
 }
 ...
} 

리스트를 단순연결리스트로 구현한 SList 클래스

public class SList <E> {
  protected Node head; // 첫 노드
  private int size; // 사이즈
  public SList(){
      head = null;
      size = 0;
  }
  // 탐색, 삽입, 삭제 연산 등 메소드 선언
} 

search (인자 탐색)

public int search(E target) {
  Node p = head;
  for (int k=0; k<size; k++){
      if(target==p.getItem()) {
          return k;
      }
      p = p.getNext();
  }
  return =1; // 탐색을 실패하면 -1 리턴
}

insertFront (맨앞에 노드 삽입)

public void insertFront(E newItem) {
  head = new Node(newItem, head);
  size++;
}

insertAfter (지정 위치에 노드 삽입)

public void insertAfter(E newItem, Node p) {
  p.setNext(new Node(newItem, p.getNext()));
  size++;
}

deleteFront (첫 노드 삭제)

public void deleteFront() {
  if(size==0){
      throw new NoSuchElementException();
  }
  head = head.getNext();
  size--; 
}

deleteAfter (지정 다음노드 삭제)

public void deleteAfter(Node p) {
  if(p==null){
      throw new NoSuchElementException();
  }
  Node t = p.getNext();
  p.setNext(t.getNext());
  t.setNext(null);
  size--; 
}

B 정리

search 메소드는 첫 노드부터 순차적으로 방문해야 하므로 O(N)시간 소요
삽입이나 삭제의 경우 각각 상수개의 레퍼런스를 갱신하므로 O(1)시간 소요
- 단, insertAfter()나 deleteAfter()의 경우에 특정 노드 p의 레퍼런스가 주어지지않으면 head로부터 찾기위해 search()를 수행해야하므로 O(N)시간 소요

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/vlDhbKH9ygM

IM

List

배열

배열로 구현한 리스트 만들기 (A)

A 정리

단순연결리스트로 구현한 리스트 만들기 (B)

B 정리