1. 리스트

• 데이터를 일렬로 늘여뜨려 놓은 형태인 선형적 자료구조이다.
• 순서를 가진다.

1.1 리스트의 연산

• 삽입
• 삭제
• 탐색

1.2 종류

• ArrayList
• LikedList
  • Single linked list
  • Double linked list
    
    

2. ArrayList

• 배열 기반의 리스트
• 메모리 공간을 연속적으로 사용

2.1 연산

• 삽입 : 삽입할 인덱스와 그 다음에 있는 데이터들을 한칸씩 뒤로 밀고 삽입, O(n)
• 삭제 : 해당 인덱스 데이터 삭제 후 삭제할 인덱스 그 다음에 있는 데이터들을 한칸씩 앞으로 당김, O(n)
• 탐색 ; random access 방식으로 탐색, O(1)

class MyArrayList<T> {
  length: number;
  elements: T[];

  constructor() {
    this.length = 0;
    this.elements = new Array<T>(0);
  }
  
  // 요소 추가
  add(t: T): void {
    this.elements[this.length] = t;
    this.length += 1;
  }
  
  // 특정 인덱스에 요소 추가
  insert(index: number, t: T): void {
    for (let i = index; i < this.length; i++) {
      this.elements[i + 1] = this.elements[i];
    }
    this.elements[index] = t;
    this.length += 1;
  }
  
  // 특정 인덱스 요소 삭제
  deleteByIndex(index: number): boolean {
    if (index < 0 || index > this.length - 1) return false;
    for (let i = index; i < this.length - 1; i++) {
      this.elements[i] = this.elements[i + 1];
    }
    this.length -= 1;
    return false;
  }
 
  // 특정 요소 삭제
  delete(t: T): boolean {
    for (let i = 0; i < this.length; i++) {
      if (this.elements[i] === t) {
        for (let j = i; j < this.length - 1; j++) {
          this.elements[j] = this.elements[j + 1];
        }
        this.length--;
        return true;
      }
    }
    return false;
  }
  
  // 특정 인덱스 요소 취득
  get(index: number): T {
    if (index < 0 || index > this.length - 1) {
      throw new Error("IndexOutOfBoundsException");
    }
    return this.elements[index];
  }
  
  // 특정 요소 인덱스 취득
  indexOf(t: T): number {
    for (let i = 0; i < this.length; i++) {
      if (this.elements[i] === t) {
        return i;
      }
    }
    return -1;
  }
  
  // 특정 요소의 유무
  contains(t: T): boolean {
    for (let i = 0; i < this.length; i++) {
      if (this.elements[i] === t) {
        return true;
      }
    }
    return false;
  }
  
  // 리스트의 length 취득
  size(): number {
    return this.length;
  }
  
  // 빈 리스트인지 여부
  isEmpty(): boolean {
    return this.length === 0;
  }
  
  // length 0으로 초기화
  clear(): void {
    this.length = 0;
    this.elements = new Array<T>(0);
  }
}

3. Linked List

• linked list는 Node로 구성되어 있다.
• node는 데이터를 저장할 수 있는 필드와 다음 노드를 가리키는 next pointer를 가진 필드를 가지고 있다.
• 가장 앞에 있는 노드는 head, 가장 마지막 노드는 tail
• 배열의 복사나 재할당 없이 데이터를 추가 할 수 있다. (유연한 공간)
• 대신, random access가 불가능하기 때문에 데이터 접근시 시간 소요

3.1 연산

next pointer를 잘 조정해주어야 한다.

• 삽입 : O(n)
• 삭제 : O(1)
• 탐색 ; O(n)