[자료구조] 단일 연결리스트

HYEJIN·2023년 1월 12일

코딩테스트

알고리즘

목록 보기

2/6

연결리스트는 아래와 같은 속성을 가지고 있음
- head : 연결리스트의 시작노드를 가리킴
- tail : 연결리스트의 마지막 노드를 가리킴
- length : 총 길이
각각 노드들은 값을 가지고 있고, 다른 노드를 가리키거나 가리키지 않는 노드들의 구성으로 이루어져 있다. ( 다음 노드가 없을 경우 아무것도 없음을 의미하는 null)
데이터에 접근하기 위해 사용할 인덱스는 없기 때문에 5번째 요소에 접근할때 다이렉트로 불가능하고, 1번째→2번째→3번째 앞에서부터 순차적으로 접근하게된다.

list와 array차이

List

인덱스가 없음

노드와 다음을 가리키는 포인터로 연결된다.

무작위 접근이 불가 (index가 없기 때문)

삽입과 삭제가 쉽다.

Array

인덱스가 있음

삽입, 삭제는 소모되는 비용이 크다

특정 인덱스에서 빠르게 접근할 수 있다.

기본 구조

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

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length=0;
    }
}

큰 틀은 위와 같다.

push 메소드

push(val){
        const node = new Node(val);
        if(this.length ===0 ){ // if(!this.head)
            this.head = node;
            this.tail = node;
        }
        else{
            this.tail.next = node;
            this.tail = node;
            
        }
        this.length++;
        
        
    }

val의 값을 가지는 노드를 생성한다.
만약 this.length===0 이거나 헤드가 없을 경우는 빈 리스트임으로 시작과 끝이 새로 만들어진 노드를 가리킨다.
만약 비어있는 리스트가 아닐 경우, 리스트의 마지막에 새로운 노드를 추가하고 next 연결, 테일을 맨 끝을 가리키도록 한다.
길이를 1개 증가시킨다.

pop 메소드

pop(){
        if(!this.head) return undefined;
        let current = this.head;
        let newTail = current;

        while(current.next){
            newTail = current;
            current= current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;

        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current.val;
    }

역방향 포인터를 가지고 있지 않기 때문에 처음부터 리스트를 따라가야한다.

빈 리스트일 경우, return
끝지점에 도달할 때 까지 계속 따라가는 동시에 이전 노드가 어떤것인지를 저장해야한다.
마지막에서 두번째 노드의 next 를 null로 지정하고, tail이 마지막에서 두번째 노드를 가리키도록 한다.
길이를 하나 감소시키고, 방금 제거한 노드를 반환

shift 메소드 (맨 앞 노드 제거)

현재 헤드가 가리키고 있는 노드를 제거한 후 헤드가 가리키고 있던 리스트의 다음 노드를 가리키도록 한다.

shift(){
        if(!this.head) return undefined;
        let currentHead = this.head;

        this.head = currentHead.next;
        this.length--;
        if(this.length===0) this.tail = null;

        return currentHead.val;

    }

unshift 메소드 ( 맨 앞에 노드를 추가 )

unshift(val){
        const newNode = new Node(val);

        newNode.next = this.head;
        this.head = newNode;
        this.length++;
        if(this.length===1) this.tail = newNode;
    }

get 메소드 ( index 위치의 노드 반환)

get(idx){
        if(idx<0 || idx>=this.length) return null;
        let cnt = 0;
        let current = this.head;

        while(cnt!==idx){
            current = current.next;
            cnt ++;
        }
        return current;
    }

찾을 위치가 음수이거나 현재 리스트의 길이보다 클 경우 null 반환 처리
카운트변수 만들어서 계속 다음노드로 이동
카운트 변수가 idx와 같아지면 루프는 종료되고 해당 노드를 반환

set 메소드( index 위치의 노드 값 변경)

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

이미 구현된 get 메서드를 통해서 index위치의 노드를 가져온다.
그 노드의 값을 변경한다.
set 유무에 따른 true, false 반환

insert 메소드 ( index 위치에 추가 )

내풀이

push나 unshift 와 같은 것들을 활용하면 되었는데 생각을 못했다,,

```jsx
insert(idx,val){
        const newNode = new Node(val);
        let foundNode = this.get(idx-1);

        if(foundNode){
            newNode.next = foundNode.next;
            foundNode.next = newNode;

            if(idx===this.length) this.tail = newNode;
           
            this.length++;
            return true;
        }
        else{ // 
            newNode.next = this.head;
            this.head = newNode;
            this.length++;
            return true;
        }

        return false;
        
    }
```

insert(idx,val){
        if(idx<0 || idx>this.legnth) return false;
        if(idx === this.length ) return this.push(val); //맨마지막에 추가
        if(idx === 0) return this.unshift(val);

        let newNode = new Node(val);
        let prev = this.get(idx-1);
        let temp = prev.next;
        prev.next = newNode;
        newNode.next = temp ; 
        this.length++;
        return true;
    }

인덱스가 음수이거나, 길이보다 클 경우 false반환
- 길이보다 클 경우는 이전에 있는 노드가 없기 때문에 연결이 안된다.
인덱스가 리스트의 길이랑 같으면 맨 마지막에 추가하는 push 메서드 이용
인덱스가 0 (처음)이면 맨 처음에 추가하는 unshift 메서드 이용
중간에 값을 추가할 경우, 이전 노드를 받아온다.
이전 노드가 가리키는 값을 temp 에 저장하고, 이전 노드가 새로운 노드를 가리키게하고, 새로운 노드는temp 를 가리킨다.
추가했기때문에 길이 1 증가
성공 시 true, 실패 시 false 반환

remove 메소드
```
remove(idx){
        if(idx<0 || idx>=this.legnth) return undefined;
        if(idx === this.length ) return this.pop(); //맨마지막에 제거
        if(idx === 0) return this.shift(); // 맨 처음 제거 

        let prev = this.get(idx-1);
        let removeNode = prev.next;
        prev.next = removeNode.next;
        this.length--;
        return removeNode;
          
    }
```
- 인덱스가 음수이거나, 길이보다 크거나 같을 경우 false반환
- 인덱스가 리스트의 길이랑 같으면 맨 마지막에 삭제하는 pop 메서드 이용
- 인덱스가 0 (처음)이면 맨 처음에 삭제하는 shift 메서드 이용
- 중간 인덱스에 값을 삭제할 경우, 이전 노드를 받아온다.
- 이전 노드가 가리키는것을 제거할 노드가 아닌 제거할 노드가 가리키는 것을 지정해주어 제거할 노드와의 연결을 끊는다.
- 길이를 1개 감소시키고 삭제된 노드를 반환한다. 실패 시 undefined 반환
reverse 메소드

0부터 채워넣어야하는데 마지막 요소부터 거꾸로 접근이 안됨.

주어진 연결 리스트의 노드순서가 역으로 연결되도록 해야한다.

리스트를 따라가면서 순서를 계속 역으로 바꿔나감
```
reverse(){

        let currentNode = this.head;
        [this.head,this.tail] = [this.tail,this.head];
        
        let beforeNode = null
        let nextNode;

        while(true){
            nextNode = currentNode.next;
            
            currentNode.next=beforeNode;

            beforeNode = currentNode;
            currentNode = nextNode;

            if(!currentNode) break;
        }
    }
```
- haed와 tail을 바꾼다
- 이전 노드(beforeNode)를 null로 초기화한다.
- a → b → c 를 반대로 바꿔줘야한다
  - a<- b 로 바꾸려면 먼저 a 노드(currentNode)가 가리키는 b노드(nextNode)를 저장한다.
  - a노드(currentNode)가 이전노드(beforeNode)를 가리키게 한다.
  - 현재 위치한 (currentNode) 노드를 nextNode로 이동한다.
  - 노드가 null일 때까지 반복한다.

HYEJIN

이전 포스트

냅색 알고리즘 (Knapsack Problem)

다음 포스트

[자료구조] 단일 연결리스트

알고리즘

list와 array차이

기본 구조

냅색 알고리즘 (Knapsack Problem)

[자료구조] 이중연결리스트

0개의 댓글