싱글 링크드 리스트

2023/04/25

9 min read

COMPUTERSCIENCE

단일 연결 리스트와 Array 차이점

Array는 데이터에 index가 부여됩니다.몇 번째 데이터에 접근하겠다가 가능합니다 반면에 연결 리스트는 인덱스 없이 그냥 다수의 데이터들로 구성됩니다 3번째 노드에 접근을 하고 싶다면 첫번째, 두번째를 거쳐야지만 접근이 가능합니다

단일 연결 리스트

단일 연결 리스트는 문자열, 숫자 등 무엇이던 원하는 데이터를 저장하는 자료구조입니다 Array와는 다르게 각 데이터에 index가 존재하지않아 데이터에 바로 접근이 불가능 합니다. Array의 경우 엘레베이터를 타고 5층으로 갈 수 있지만 단일 연결리스트는 계단으로 5층을 올라가야하는 셈입니다

우선 3가지 속성을 알아보겠습니다

Head: 리스트의 시작 노드를 가리킵니다
Tail: 리스트의 마지막 노드를 가리킵니다
length: 리스트의 길이를 나타냅니다

각각의 엘리먼트들을 노드라고 부른다고 했을 때 각 노드는 "Next"라는 포인터를 통해 다음 노드와 연결되어 있고 각 노드는 문자열이나 숫자 등 데이터 가지고 있고 다음 노드를 가리키는 정보 또한 가지고있습니다, 다음 노드가 없다면 null을 저장하고 있습니다

단일 연결 리스트 구현해보기

구현 해볼 단일 연결 리스트 메소드

push
pop
shift
unshift
get
set
insert
remove
reverse

Node 만들기

리스트를 이루고 있는 Node를 먼저 만들어 보겠습니다

1
class Node {
2
  constructor(value) {
3
    this.value = value;
4
    this.next = null;
5
  }
6
}

SingleLinked 만들기

1
class SingleLinked {
2
  constructor() {
3
    this.head = null;
4
    this.tail = null;
5
    this.length = 0;
6
  }
7
}

push 매서드

1
push(value){
2
  const newNode = new Node(value)
3
  if(!this.head){
4
    this.head = newNode;
5
    this.tail = this.head;
6
  }else{
7
    this.tail.next = newNode;
8
    this.tail = newNode;
9
  }
10

11
  this.length++;
12

13
  return this;
14
}

노드를 뒤쪽으로 추가하는 메서드입니다

class Node를 이용하여 새로운 노드 인스턴스를 만들고 첫 push 케이스와 그 외 나머지로 분기를 나누어 처리합니다.

tail의 next는 null값이기 때문에 next값을 새로 만든 newNode로 정하고 this.tail의 값을 새로만든 노드로 변경해줍니다

pop 메서드

1
pop(){
2
  if(this.head) return undefined
3
  let current = this.head;
4
  let previous = current;
5

6
  while(current.next){
7
    previous = current;
8
    current = current.next;
9
  }
10

11
  this.tail = previous;
12
  this.tail.next = null;
13
  this.length--;
14

15
  if(this.length === 0){
16
    this.head = null;
17
    this.tail = null;
18
  }
19
  return current;
20
}

마지막 노드를 제거하는 메서드입니다

this.head를 시작으로 이전 노드와 현재 노드를 저장하면서 전체 노드를 순회합니다

current 노드의 next가 null이라면 마지막 노드여서 삭제시켜야할 노드입니다. previous 노드의 next를 null로 변경하여 현재 노드를 삭제 시켜줍니다 노드의 tail도 바뀌어야 하기 때문에 this.tail도 previous로 변경해줍니다

shift 매서드

1
shift(){
2
  if(!this.head) return undefined;
3
  const previous = this.head;
4
  this.head = previous.next;
5
  this.length--;
6

7
  if(this.length === 0){
8
    this.tail = null;
9
  }
10

11
  return previous;
12
}

앞쪽의 노드를 꺼내는 매서드로 this.head가 가리키는 노드를 previous에 저장하고 this.head는 previous의 next를 가리키도록 설정해줍니다 this.length가 0이라면 모든 데이터가 없으므로 this.tail이 가리키고 있는 값을 null로 변경합니다

unshift 매서드

1
unshift(value){
2
  const newNode = new Node(value);
3
  if(!this.head){
4
    this.head = newNode;
5
    this.tail = this.head;
6
  }else{
7
    newNode.next = this.head;
8
    this.head = newNode;
9
  }
10
  this.length++;
11

12
  return this;
13

14
}

앞쪽에 노드를 추가하는 메서드입니다 새로운 노드를 만들고 this.head를 저장하고 새로만든 노드의 next가 가리키도록 합니다 this.head는 새로운 노드를 가리키도록 합니다

get 매서드

1
get(index){
2
  if(index < 0 || index > this.length) return undefined;
3
  let count = 0;
4
  let findNode = this.head;
5

6
  while(count < index){
7
    findNode = findNode.next;
8
    count++;
9
  }
10

11
  return findNode
12
}

찾고자 하는 index번호의 데이터를 찾아 반환하는 매서드입니다

바로 해당 index에 접근할 수 없기 때문에 this.head를 시작으로 count를 세어가면서 index에 도착하면 찾아낸 Node를 반환합니다

set 매서드

1
set(index,value){
2
  const foundNode = this.get(index);
3

4
  if(foundNode){
5
    foundNode.value = value;
6
    return true;
7
  }
8

9
  return false;
10
}

해당 index의 노드의 value값을 변경하는 매서드입니다 get매서드를 이용하여 node를 찾고 value를 변경해줍니다

insert 매서드

1
insert(index, value){
2
  if(index < 0 || index > this.length) return false;
3
  if(index === this.length) return !!this.push(value);
4
  if(index === 0) return !!this.unshift(value);
5

6
  const newNode = new Node(value);
7
  const previousNode = this.get(index - 1);
8
  const temp = previousNode.next;
9

10
  previousNode.next = newNode;
11
  newNode.next = temp;
12
  this.length++;
13

14
  return true;
15
}

해당 index에 value를 가진 노드를 추가하는 매서드입니다.

index가 제일 앞이나 뒤라면 만들어둔 매서드를 사용하여 추가합니다 원하는 index의 이전 node를 this.get 매서드를 이용하여 previousNode에 저장하고 previousNode 노드의 next도 temp에 저장해둡니다.

원하는 index 이전의 노드의 next는 새로만든 Node 새로만든 Node의 next를 temp로 지정해줍니다

remove 매서드

1
remove(index){
2
  if(index < 0 || index > this.length) return undefined;
3
  if(index === 0) return this.shift();
4
  if(index === this.length) return this.pop();
5

6
  const foundNode = this.get(index - 1);
7
  const removed = foundNode.next;
8
  foundNode.next = removed.next;
9
  this.length--;
10

11
  return removed;
12
}

해당 index에 위치한 node를 제거하는 매서드입니다 원하는 index의 이전 노드를 찾아 foundNode에 저장해줍니다 삭제할 노드를 저장해주고 foundNode의 next를 삭제할 노드의 next값으로 변경해줍니다

reverse 매서드

1
reverse(){
2
  let currentNode = this.head
3
  let previousNode = null
4
  let nextNode;
5
  this.head = this.tail
6
  this.tail = currentNode;
7
  for(let i = 0; i < this.length; i++){
8
    nextNode = currentNode.next;
9
    currentNode.next = previousNode;
10
    previousNode = currentNode;
11
  }
12
  return this
13
}

리스트를 역방향으로 바꿔주는 매서드입니다

시작점을 가질 currentNode 이전값을 가질 previous노드 초기값은 null head부분이 tail이 되어야하기 때문에 null로 초기값을 둡니다 역방향으로 지정을 해야하기 때문에 다음 노드를 저장해둘 nextNode 변수를 생성해줍니다

this.head는 this.tail로 this.tail은 this.head 값으로 변경시켜줍니다

리스트 길이만큼 순회하면서 nextNode에 현재 노드의 다음 노드 값을 저장시키고 현재 노드의 next는 이전 노드를 바라볼 수 있도록 해줍니다 previous노드의 값은 현재 노드값을 저장함으로써 이전 노드의 값을 저장해줍니다

한동룡

싱글 링크드 리스트

단일 연결 리스트#

단일 연결 리스트 구현해보기#

Node 만들기#

SingleLinked 만들기#

push 매서드#

pop 메서드#

shift 매서드#

unshift 매서드#

get 매서드#

set 매서드#

insert 매서드#

remove 매서드#

reverse 매서드#