연결리스트(Linked List)

1. 자기 참조 구조체

• 동일한 타입의 다른 구조체에 대한 포인터를 멤버로 포함하는 구조체
• 여러 개의 노드로 이루어진다.
• 각각의 노드는 데이터와 다음 노드가 뭔지 알려주는 주소를 갖는다
• 새로운 데이터를 추가 및 위치를 찾거나 제거하는 기능이 있다,
• 이미 js에선 배열로 다 구현되어있음.

const LinkedList = () => {
  function LinkedList() {
    this.length = 0;
    this.head = null;
  }
  function Node(data) {
    this.data = data;
    this.next = null
  }
  return LinkedList;
}

• LinkList에는 length와 head 변수가 있으며, 각각 노드의 갯수와 첫 노드의 주소를 가리키고 있다.

2. 연결리스트 추가,검색,삭제 구현

const LinkedList = () => {
  function LinkedList() {
    this.length = 0;
    this.head = null;
  }
  function Node(data) {
    this.data = data;
    this.next = null
  }

// add
LinkedList.prototype.add = value => {
  let node = new Node(value);
  let current = this.head;
  //현재 연결리스트에 아무 노드도 없다면,
  if(!current) {
    // head에 새 노드 추가해주고, 길이를 1증가
    this.head = node;
    this.length++;
    return node;
  } else { //노드가 있다면,
    while(current.next) { // 마지막 노드를 찾는다
      current = current.next;
    }
    current.next = node; // 마지막 노드위치에 노드를 추가
    this.length++;
    return node;
};
  
LinkedList.prototype.search = position => {
  let current = this.head;
  let count = 0;
  while(count < position) {
    current = current.next;
    count++;
  }
  return current.data
};
  
LinkedList.prototype.remove = position => {
  let current = this.head;
  let before, remove;
  let count = 0;
  
  if(position === 0) { // 맨 처음 노드 삭제시
    remove = this.head;
    this.length--;
    return remove;
  } else { // 그 외의 노드를 삭제하면
    while(count < position) {
      before = current;
      count++;
      current = current.nextl
    }
    remove = current;
    before.next = current.next;
    // remove 메모리정리
    this.length--;
    return remove;
  }
};
  return LinkedList;
}();