자료구조-list

치맨·2022년 12월 31일
자료구조
0

알고리즘,자료구조

목록 보기
4/11
post-thumbnail

목차

List란

  • 배열의 가장 큰 특징은 인덱스를 통해 데이터를 찾을 수 있지만,
    배열의 요소를 추가, 삭제할 경우 메모리가 커지는 단점이 있습니다.

  • List는 배열이 가지고 있는 인덱스라는 장점을 버리고, 빈틈없는 데이터의 적재라는 장점을 취한 자료구조입니다.

  • 배열의 경우 어떤 엘리먼트가 삭제되면 삭제된 상태를 빈 공간으로 남겨두지만, List의 경우 빈공간을 남겨두지 않고 값을 채웁니다.

  • 따라서 List에서 인덱스는 중요하지 않습니다. List 자료구조의 핵심은 엘리먼트들 간의 순서입니다. 그래서 리스트를 다른 말로는 시퀀스(sequence)라고도 부릅니다. 시퀀스는 순서라는 의미죠. 즉 순서가 있는 데이터의 모임입니다.

  • 데이터가 순차적으로 저장되기 때문에 끊어지지 않으며, 한 줄로 계속되기 때문에 마치 선과 같은 형태를 띈다 하여 선형 구조라고 합니다.

  • 자바스크립트에서는 배열의 기능에 List 기능을 포함하고 있습니다.

List의 기능

아래의 3가지 기능을 가지고 있고, 순서가 있으면서 중복이 허용된다면 List자료구조라고 할 수 있습니다

  • 처음, 끝, 중간에 엘리먼트를 추가/삭제하는 기능
  • 리스트에 데이터가 있는지를 체크하는 기능
  • 리스트의 모든 데이터에 접근할 수 있는 기능

List의 장점과 단점

  • List의 장점

    • 리스트의 가장 큰 장점이라면 크기가 가변이라는 것입니다. 원소의 추가와 삭제에 따라 크기가 동적으로 변하기 때문에 연속적으로 메모리를 할당할 필요가 없고, 사용한 메모리도 재사용이 가능하여 메모리의 낭비가 적습니다.

    • 따라서 삽입과 삭제가 빈번한 데이터를 관리할 경우 사용되면 좋은 자료구조입니다.

  • List의 단점

    • 배열과 비교했을때 값을 탐색하는데 시간이 소요됩니다. 첫 항목부터 순차적으로 접근하므로 최대 O(n)의 시간이 걸립니다.
    • 별도의 주소를 저장하는 공간을 필요로 하기 때문에 추가적인 메모리가 필요한 점이 있다.
    • 따라서 자료를 탐색하는 경우 별로 좋지 않습니다.

List의 종류

  • 선형리스트(ArrayList)

    • 배열을 이용하여 구현하기 때문에 원소들의 논리적인 순서와 메모리에 저장되는 물리적인 순서가 같다는 특징이 있습니다.
    • 데이터를 순서대로 나열해 놓은 자료 구조입니다.
    • 메모리에 연속으로 할당되기에 접근 속도가 매우 빠릅니다.
    • 데이터 삽입, 삭제 시 데이터의 이동이 필요하기에 시간이 많이 걸립니다.
    • 배열을 이용하여 구현하기 때문에 제한된 크기를 가지며, 메모리 사용의 비효율성 문제를 갖습니다.

  • 연결리스트(Linked List)

    • 노드(Node)라는 요소로 구성되어 있으며, 데이터와 다음 노드를 가리키는 포인터를 가지며, 노드와 노드를 한줄로 연결된 연결리스트를 만듭니다.
    • 추가와 삭제가 될 경우 해당 노드가 가리키는 포인트만 변경하기 때문에 시간복잡도가 O(1)입니다.
    • 데이터를 검색시 최악의 경우 모든 요소를 탐색해야 하기 때문에 시간복잡도가 O(n)시간이 걸립니다.
    • 가장 첫번째 노드를 Head라고 하며, 맨 마지막 노드를 Tail 이라고 합니다.

  • 단순연결리스트(Single Linked List)

    • 연결리스트 중 하나로서 Head부터 Tail까지 탐색하는 방향이 단방향입니다.

    • Head부터 Tail까지 차례차례 노드를 탐색하기 때문에 비용도 크고, 속도도 느립니다.

    • 새로운 노드를 추가할 경우 추가, 삭제, 삽입이 간편합니다.

      ADT설명
      isEmpty()list가 비어있는지 확인
      insertHead(data)Head에 값(data)을 추가
      insertTail(data)Tail에 값(data)을 추가
      insert(data, index)원하는위치(index)에 값(data)을 추가
      getAt(index)원하는위치(index)의 값을 찾기
      remove(index)원하는위치(index)의 값을 제거
      clear()list 초기화
      print()list 출력
      class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class SingleLinkedList {
  constructor() {
    this.head = null; //처음에 데이터가 없다면 head는 null이다.
    this.tail = null;
    this.size = 0; //리스트의 크기를 나타내며, 초기값은 0이다.
  }

  isEmpty() {
    return this.size == 0;
  }

  insertHead(data) {
    if (this.isEmpty()) {
      this.head = new Node(data);
      this.size++;
    } else {
      let current = this.head;
      this.head = new Node(data);
      this.head.next = current;
      this.size++;
    }
  }

  insertTail(data) {
    let newNode = new Node(data);
    if (this.isEmpty()) {
      this.head = new Node(data);
      this.size++;
    } else {
      let current = this.head;

      while (current.next) {
        // tail을 찾아준다.
        current = current.next;
      }

      current.next = newNode; // next가 null === tail 이므로 newNode를 넣어준다.
    }
    this.size++; //length 는 1증가
  }

  insert(data, index) {
    if (index > 0 && index > this.size) {
      console.log('범위를 벗어났습니다');
      return;
    }
    // 범위를 벗어나면 종료해준다.
    if (index === 0) {
      let current = this.head;
      this.head = new Node(data);
      this.head.next = current;
      this.size++;
      return;
    }

    let currentNode = this.head;
    let newNode = new Node(data);
    let count = 0;
    let temp;

    while (count < index - 1) {
      count++;
      currentNode = currentNode.next;
    }

    temp = currentNode.next;
    currentNode.next = newNode;
    newNode.next = temp;

    this.size++;
  }

  getAt(index) {
    let currentNode = this.head;
    let count = 0;

    if (currentNode === null) return null;
    while (currentNode) {
      if (count == index) {
        console.log(currentNode.data);
      }
      count++;
      currentNode = currentNode.next;
    }
    return null;
  }

  remove(index) {
    if (index > 0 && index > this.size) {
      console.log('범위를 벗어났습니다');
      return;
    }

    let currentNode = this.head;

    let count = 0;

    // Remove first
    if (index === 0) {
      this.head = currentNode.next;
    } else {
      //loop를 통해 해당 index의 연결고리를 끊는다.
      while (count < index - 1) {
        count++;
        currentNode = currentNode.next;
      }

      currentNode.next = currentNode.next.next;
    }

    this.size--;
  }

  clear() {
    this.head = null;
    this.size = 0;
  }

  print() {
    let result = '';
    let currentNode = this.head;

    if (currentNode === null) return null;
    while (currentNode.next) {
      result += `${currentNode.data} `;
      currentNode = currentNode.next;
    }
    result += currentNode.data;

    console.log(result);
  }
}
const linkedList = new SingleLinkedList();

// isEmpty Test

console.log(linkedList.isEmpty()); // true 출력

// insertHead Test

linkedList.insertHead(100);
linkedList.print(); // 100 출력

linkedList.insertHead(200);
linkedList.print(); // 200 100 출력

linkedList.insertHead(300);
linkedList.print(); // 300 200 100 출력
console.log(linkedList.isEmpty()); // false 출력

// insertTail Test
linkedList.insertTail(400);
linkedList.print(); // 300 200 100 400 출력

linkedList.insert(500, 2);
linkedList.insert(900, 4);
linkedList.print(); // 300 200 500 100 400 출력

linkedList.getAt(3); // 100 출력

linkedList.remove(1);
linkedList.print(); // 300 200 500 400 출력

linkedList.clear();
linkedList.insertHead(100);
linkedList.print(); // 100 출력

  • 이중연결리스트(Doubly Linked List)

    • Head에서 Tail, Tail에서 Head로 양방향 탐색을 합니다. 즉 포인터가 이전 노드(prev)와 다음 노드(next) 두개를 가리킵니다.

    • 노드별로 이전과 다음 부분을 고려해서 코드를 구성해야 하기때문에 메모리 저장공간이 더 필요하다는 단점이 있습니다.

      class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null; //처음에 데이터가 없다면 head는 null이다.
    this.tail = null;
    this.size = 0; //리스트의 크기를 나타내며, 초기값은 0이다.
  }

  isEmpty() {
    return this.size == 0;
  }

  insertHead(data) {
    if (this.isEmpty()) {
      this.head = new Node(data);
      this.size++;
    } else {
      let current = this.head;
      let newNode = new Node(data);
      this.head = newNode;
      newNode.next = current;
      current.prev = newNode;
      this.size++;
    }
  }

  insertTail(data) {
    let newNode = new Node(data);

    if (this.isEmpty()) {
      this.head = new Node(data);
      this.size++;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }

      current.next = newNode; // next가 null === tail 이므로 newNode를 넣어준다.
      newNode.prev = current;
    }
    this.size++; //length 는 1증가
  }

  insert(data, index) {
    if (index > 0 && index > this.size) {
      console.log('범위를 벗어났습니다');
      return;
    }
    // 범위를 벗어나면 종료해준다.
    if (index === 0) {
      let current = this.head;
      let newNode = new Node(data);
      this.head = newNode;
      newNode.next = current;
      current.prev = newNode;
      this.size++;
      return;
    }

    let currentNode = this.head;
    let newNode = new Node(data);
    let count = 0;
    let temp;

    while (count < index - 1) {
      count++;
      currentNode = currentNode.next;
    }

    temp = currentNode.next;
    currentNode.next = newNode;
    newNode.next = temp;
    newNode.prev = currentNode;

    this.size++;
  }

  getAt(index) {
    let currentNode = this.head;
    let count = 0;

    if (currentNode === null) return null;
    while (currentNode) {
      if (count == index) {
        console.log(currentNode.data);
      }
      count++;
      currentNode = currentNode.next;
    }
    return null;
  }

  remove(index) {
    if (index > 0 && index > this.size) {
      console.log('범위를 벗어났습니다');
      return;
    }

    let currentNode = this.head;

    let count = 0;

    // Remove first
    if (index === 0) {
      this.head = currentNode.next;
    } else {
      //loop를 통해 해당 index의 연결고리를 끊는다.
      while (count < index) {
        count++;
        currentNode = currentNode.next;
      }

      let temp;

      temp = currentNode.next;
      currentNode.prev.next = temp;
    }

    this.size--;
  }

  clear() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  print() {
    let result = '';
    let currentNode = this.head;

    if (currentNode === null) return null;
    while (currentNode.next) {
      result += `${currentNode.data} `;
      currentNode = currentNode.next;
    }
    result += currentNode.data;

    console.log(result);
  }
}
const linkedList = new DoublyLinkedList();

// isEmpty Test

console.log(linkedList.isEmpty()); // true 출력

// insertHead Test

linkedList.insertHead(100);
linkedList.print(); // 100 출력

linkedList.insertHead(200);
linkedList.print(); // 200 100 출력

linkedList.insertHead(300);
linkedList.print(); // 300 200 100 출력
console.log(linkedList.isEmpty()); // false 출력

// insertTail Test
linkedList.insertTail(400);
linkedList.print(); // 300 200 100 400 출력

linkedList.insert(500, 2);
linkedList.insert(900, 0);
linkedList.print(); // 900 300 200 500 100 400 출력

linkedList.getAt(3); // 500 출력

linkedList.remove(0);
linkedList.print(); // 300 200 500 100 400 출력

linkedList.remove(2);
linkedList.print(); // 300 200 100 400 출력

linkedList.clear();
linkedList.insertHead(100);
linkedList.print(); // 100 출력

  • 원형(환형)연결리스트

    • Head와 Tail이 연결되어 순환(Circular) 구조를 지닙니다. 즉 Tail의 다음값은 Head가 됩니다.
    • 연결리스트에서 Head와 Tail을 연결한 구조입니다.
   class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null; //처음에 데이터가 없다면 head는 null이다.
    this.tail = this.head;
    this.size = 0; //리스트의 크기를 나타내며, 초기값은 0이다.
  }

  isEmpty() {
    return this.size == 0;
  }

  insertHead(data) {
    if (this.isEmpty()) {
      this.head = new Node(data);
      this.size++;
    } else {
      let current = this.head;
      let newNode = new Node(data);
      this.head = newNode;
      newNode.next = current;
      current.prev = newNode;
      this.size++;
    }
  }

  insertTail(data) {
    let newNode = new Node(data);

    if (this.isEmpty()) {
      this.head = new Node(data);
      this.size++;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }

      current.next = newNode; // next가 null === tail 이므로 newNode를 넣어준다.
      newNode.prev = current;
    }
    this.size++; //length 는 1증가
  }

  insert(data, index) {
    if (index > 0 && index > this.size) {
      console.log('범위를 벗어났습니다');
      return;
    }
    // 범위를 벗어나면 종료해준다.
    if (index === 0) {
      let current = this.head;
      let newNode = new Node(data);
      this.head = newNode;
      newNode.next = current;
      current.prev = newNode;
      this.size++;
      return;
    }

    let currentNode = this.head;
    let newNode = new Node(data);
    let count = 0;
    let temp;

    while (count < index - 1) {
      count++;
      currentNode = currentNode.next;
    }

    temp = currentNode.next;
    currentNode.next = newNode;
    newNode.next = temp;
    newNode.prev = currentNode;

    this.size++;
  }

  getAt(index) {
    let currentNode = this.head;
    let count = 0;

    if (currentNode === null) return null;
    while (currentNode) {
      if (count == index) {
        console.log(currentNode.data);
      }
      count++;
      currentNode = currentNode.next;
    }
    return null;
  }

  remove(index) {
    if (index > 0 && index > this.size) {
      console.log('범위를 벗어났습니다');
      return;
    }

    let currentNode = this.head;

    let count = 0;

    // Remove first
    if (index === 0) {
      this.head = currentNode.next;
    } else {
      //loop를 통해 해당 index의 연결고리를 끊는다.
      while (count < index) {
        count++;
        currentNode = currentNode.next;
      }

      let temp;

      temp = currentNode.next;
      currentNode.prev.next = temp;
    }

    this.size--;
  }

  clear() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  print() {
    let result = '';
    let currentNode = this.head;

    if (currentNode === null) return null;
    while (currentNode.next) {
      result += `${currentNode.data} `;
      currentNode = currentNode.next;
    }
    result += currentNode.data;

    console.log(result);
  }
}
const linkedList = new DoublyLinkedList();

// isEmpty Test

console.log(linkedList.isEmpty()); // true 출력

// insertHead Test

linkedList.insertHead(100);
linkedList.print(); // 100 출력

linkedList.insertHead(200);
linkedList.print(); // 200 100 출력

linkedList.insertHead(300);
linkedList.print(); // 300 200 100 출력
console.log(linkedList.isEmpty()); // false 출력

// insertTail Test
linkedList.insertTail(400);
linkedList.print(); // 300 200 100 400 출력

linkedList.insert(500, 2);
linkedList.insert(900, 0);
linkedList.print(); // 900 300 200 500 100 400 출력

linkedList.getAt(3); // 500 출력

linkedList.remove(0);
linkedList.print(); // 300 200 500 100 400 출력

linkedList.remove(2);
linkedList.print(); // 300 200 100 400 출력

linkedList.clear();
linkedList.insertHead(100);
linkedList.print(); // 100 출력

Ref

profile
치맨
기본기가 탄탄한 개발자가 되자!
이전 포스트

자료구조- 배열

다음 포스트

자료구조-Stack

0개의 댓글