Skip to content

11.Singly Linked Lists.md

Latest commit

 

History

History
364 lines (278 loc) · 8.87 KB

11.Singly Linked Lists.md

File metadata and controls

364 lines (278 loc) · 8.87 KB

Singly Linked Lists

목표

  • Singly Linked Lists가 무엇인지 알아봅시다.
  • 배열과 리스트의 비교해봅니다.
  • 삽입, 삭제, 순회를 구현해봅시다.

linked list란 무엇 일까요?

일종의 자료 구조로 머리부터 꼬리까지 프로퍼티로 연결된 것을 말합니다.

Linked Lists는 노드들로 이루어져 있는데 각 노드들은 마치 기차처럼 순차적으로 연결 되어 있습니다.

하지만 배열과 다르게 index란 것이 없습니다.

  • 예

    4(head)-6-8-2(tail) 마지막은 null과 연결됐습니다. 길이는 4입니다.

Linked list vs Arrays

Lists

  • 인덱스가 없습니다.
  • 다음을 가르키는 포인터로 각 노드들이 연결되어 있습니다.
  • Random 접근이 불가합니다.

Arrays

  • 순서데로 인덱스가 있습니다.
  • 삽입과 삭제가 복잡합니다.
  • 특정 인덱스에 접근하기가 쉽습니다.

List의 장점은 삽입과 삭제가 쉽다는 것입니다!

Singly Linked Lists 구현

1. Pusing

  1. 이 함수는 값을 받습니다.
  2. 이 함수의 인자로 새 노드를 만듭니다.
  3. 만약 list에 head가 없으면 head를 설정하고 tail이 새로운 노드가 됩니다.
  4. 그렇지 않다면 tail옆에 새로운 노드를 만들고 새로 생긴 노드를 tail로 지정합니다.
  5. 길이를 1 증가시킵니다.
  6. Linked LIsts를 return 합니다.

  • 구현

    // 데이터 조각 : val
// 다음 노드 레퍼런스 : next

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
    
  // node push function
  push(val) {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }
    // 마지막 찾는 함수
    traverse() {
		let current = this.head;
        while(current) {
			console.log(current.val);
            current = current.next
        }
    }
}

2. Popping

Linked LIst 마지막 노드를 삭제하고 리턴하는 함수입니다.

의사코드

  1. 만약 노드가 없다면 undefined를 return 합니다.
  2. tail에 닿을때 까지 Loop를 진행합니다.
  3. 마지막 노드 바로 전 노드의 next를 null을 지정합니다.
  4. 마지막 전 노드를 tail로 설정합니다.
  5. 제거된 노드를 return 합니다.

Popping 구현

  pop() {
    // 1. 아무것도 없으면 undefined 리턴
    if (!this.head) return undefined;
    // 2. current라는 변수에 헤드를 설정
    let current = this.head;
    // 3. newTail에 current를 할당
    let newTail = current;
    //  4. 끝을 찾기위해 while
    while (current.next) {
      newTail = current;
      current = current.next;
    }
    // 5. tail newTail을 할당
    this.tail = newTail;
    // 6. 마지막을 끊음
    this.tail.next = null;
    // 7. 길이 줄이기
    this.length--;
    // 아무 요소가 없으면 head와 tail을 null로
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    // 8. 삭제한 값 리턴
    return current;
  }

3. Shifting

Linked List 제일 앞 노드를 삭제하는 메소드 입니다.

의사코드

  1. 노드가 없다면, undefined를 return 합니다.
  2. 현재 head 프로퍼티를 임시로 저장 합니다.
  3. head를 지금 head의 다음 프로퍼티로 지정합니다.
  4. 길이를 1 줄입니다.
  5. 제거된 노드의 값을 return 합니다.

Shifting 구현

shift() {
    if (!this.head) return undefined;
    let currentHead = this.head;
    this.head = currentHead.next;
    this.length--;
    return currentHead;
}

4. Unshifting

맨 앞에 새 head 노드를 생성합니다.

의사코드

  1. 인자를 받습니다.
  2. 받은 인자로 새 노드를 생성합니다.
  3. head가 없으면 head와 tail을 새로 생성된 노드를 지정합니다.
  4. head가 있다면 새로 생성된 노드의 next 프로퍼티를 원래 존재하던 head의 값으로 설정합니다.
  5. 새로 생성된 노드를 head로 지정합니다.
  6. 길이를 1 증가 시킵니다.
  7. linked list를 return 합니다.

Unshifting 구현

unshift(val) {
	let newNode = new Node(val);
    if(!this.head) {
        this.head = newNode;
        this.tail = this.head;
    } else {
        newNode.next = this.head;
        this.head = newNode;
    }
    this.length++;
    return this;
}

5. Get

숫자로 linked list의 위치를 찾는 메소드 입니다.

Get 의사코드

  1. index값을 인자로 받습니다.
  2. 만약 index가 0보다 작거나 길이보다 같거나 크면 null을 return 합니다.
  3. 인자로 받은 index 숫자만큼 loop를 하고 그 index의 노드를 return 합니다.

Get 구현

get(index) {
    if(index < 0 || index >= this.length) return null;
    let counter = 0;
    let current = this.head;
    while(couter !== index) {
        current = current.next;
        counter++
    }
    return current;    
}

6. Set

위치를 기준으로 해당 노드의 값을 바꾸는 메소드 입니다.

Set 의사코드

  1. 함수는 값과 index 두개를 인자로 받습니다.
  2. 주어진 index와 get 함수를 이용해서 특정 노드를 찾습니다.
  3. 만약 노드가 없으면 false를 return 합니다.
  4. 만약 노드가 있으면, 새로 받은 값을 해당 노드 값으로 재 설정하고 true를 return 합니다.

Set 구현

set(index, val) {
    let foundNode = this.get(index);
    if(foundNode){
        foundNode.val = val;
        return true;
    }
    return false;
}

7. Insert

특정 위치에 노드를 추가하는 메소드 입니다.

Insert 의사코드

  1. 만약 index가 0보다 작거나 length보다 크면 return false를 한다.
  2. 만약 index가 length와 같으면 마지막에 새 노드를 추가합니다.
  3. 만약 index가 0이면, unshift메소드를 사용해서 list 시작 부분에 노드를 추가합니다.
  4. 위 경우가 아니라면 get메소드를 활용해서 주어진 index-1에 접근합니다.
  5. get으로 얻은 노드의 next 프로퍼티로 새 노드를 설정합니다.
  6. 새 노드의 next 프로퍼티는 이전의 next 프로퍼티로 설정합니다.
  7. length를 1 증가시킵니다.
  8. Return true

Insert 구현

insert(index, val) {
    if(index < 0 || index > this.length) return false;
    if(index === this.length) return !!this.push(val);
    if(index === 0) return !!this.unshift(val);
    let newNode = new Node(val);
    let prev = this.get(index - 1);
    let temp = prev.next;
    prev.next = newNode;
    newNode.next = temp;
    this.length++;
    return true;
}

8. Remove

특정 위치에 있는 노드를 제거합니다.

의사코드

  1. 만약 index가 0보다 작거나 length보다 길면 undefined를 return 합니다.
  2. 만약 index가 length-1과 같으면 pop 메소드를 사용합니다.
  3. 만약 index가 0이라면 shift메소드를 사용합니다.
  4. 위 조건이 아니라면 get메소드에 index-1을 넣어줍니다.
  5. get으로 얻은 노드의 다음 다음 노드를 next 노드로 설정합니다.
  6. length를 1 감소시킵니다.
  7. 제거한 노드를 return 합니다.

remove 구현

remove(index) {
	if(index < 0 || index >= this.length) return undefined;
    if(index === 0) return this.shift();
    if(index === this.length - 1) return this.pop();
    let previousNode = this.get(index - 1);
    let removed = previousNode.next;
    previousNode.next = removed.next;
    this.length--;
    
    return removed;
}

9. Reverse

말 그대로 list의 순서를 뒤집는 메소드 입니다.

의사코드

  1. head와 tail을 바꿉니다.
  2. next라는 변수를 만듭니다.
  3. prev라는 변수를 만듭니다.
  4. node라는 변수를 만들고 head를 할당 합니다.
  5. list를 Loop 합니다.
  6. node

reverse 구현

  • 배열을 log하는 print 함수 만들기

    print() {
    let arr = [];
    let current = this.head;
    while(current) {
		arr.push(current.val);
        current = current.next;
    }
    console.log(arr;)
}

  • reverse 함수

    reverse() {
    let node = this.head;
    this.head = this.tail;
    this.tail = node;
    let next;
    let prev = null;
    for(let i = 0; i < this.length) {
	   next = node.next;
        node.next = prev;
        prev = node;
        node = next;
    }
    return this;
}

Singly Linked Lists Big O 표기법

  • Insertion : O(1)
  • Removal : It depends ... O(1) or O(N)
  • Searching : O(N)
  • Access : O(N)