■ linked list의 종류
1. 단일(단방향) 연결 리스트
2,. 이중(양방향) 연결 리스트
3. 원형 연결 리스트
위 세가지 중 기본적인 "단일 연결 리스트"를 먼저 이해해보기로 하자.
■ 특징
1. 각 노드는 다음 노드를 가리키는 포인터를 포함한다. 그리고 다음 노드를 가리키는 포인터는 "다음 노드의 주소"를 값으로 가지고 있다.
■ 코드로 구현
// 노드 생성
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
// 리스트 생성
class LinkedList {
constructor() {
this.head = null;
this.length = 0;
}
}
노드/리스트 만들기
1. 우선 리스트를 채워줄 노드를 만드는 부분이다. class를 사용해 노드들을 독립적인 객체 인스턴스로 만든다. 노드의 프로퍼티로는 data, next가 있다. data는 말 그대로 값을 의미하고, next는 linked list를 구현하는데 제일 중요한 "다음 노드에 대한 정보(주소)"가 담겨있다.
2. linked list의 몸체이다. 노드들이 생성되어 채워질 공간이다. linked list에는 head라고 있는데, 리스트의 제일 첫 번째 요소이다.
3. 리스트의 길이 length. 리스트에 몇개의 노드가 있는지 범위를 알 수 있다.
class LinkedList {
constructor(){
this.head = null;
this.length = 0;
}
/* search 부분 */
getAt(){}
/* insert 부분 */
inserFirst(){}
inserLast(){}
insertAt(){}
/* remove 부분 */
removeAt(){}
}
↑ 조회/삽입/삭제
1. 데이터를 조회/삽입/삭제는 리스트 안에서 이루어지기 때문에 LinkedList의 메서드로 만들어 보자.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor(){
this.head = null;
this.length = 0;
}
/* insert 부분 */
insertFirst(data) {
this.head = new Node(data, this.head)
this.length++;
}
}
↑ 앞에서 부터 삽입 insertFirst
1. head의 값이 계속 바뀐다. 만약 기존에 head가 있다면, 그 head는 이제 앞으로 삽입 될 head의 next가 되어 head의 다음 노드가 된다.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor(){
this.head = null;
this.length = 0;
}
insertLast(data) {
let node = new Node(data);
let current;
// #1
if (!this.head) {
this.head = node;
} else {
current = this.head;
// #2
while (current.next) {
current = current.next;
}
// #3
current.next = node
}
this.length++;
}
}
↑ 뒤에서 부터 삽입 insertLast
#1 - linked list의 특성상 앞에서 부터 순차적으로 데이터를 검색해야 한다.
#2 - while 반복문으로 노드들의 next 값을 순차적으로 확인한다. 만약 next의 값이 null이라면 그 노드는 list의 tail 부분임을 알 수 있다.
#3 - list의 tail 부분을 찾았으니 새로운 노드를 넣을 수 있다.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor(){
this.head = null;
this.length = 0;
}
insertAt(data, index) {
// #1
if (index > 0 && index > this.index) {
return;
}
if (index === 0) {
this.head = new Node(data, this.head)
this.length++
return;
}
const node = new Node(data);
let current, previous;
current = this.head;
let count = 0;
// #2
while (count < index) {
previous = current;
count++;
current = current.next;
}
// #3
node.next = current;
previous.next = node;
this.length++;
}
}
↑ 중간에 삽입 insertAt
#1 - 사용자가 입력한 위치가 만약 리스트에 없을때. 리스트 안에 있는 노드들의 갯수(범위)를 넘어갔을때는 새로운 노드를 삽입하면 안된다.
#2 - 사용자가 삽입할 위치의 노드는 previous가 되고, 이제 삽입될 노드는 current로 정의한다. 그리고 current 노드의 next는 previous의 next가 될 것이다. 즉, previous 노드를 바탕으로 노드의 연결고리가 수정된다는 의미다.
#3 - 사용자의 위치값을 바탕으로 while 반복문을 사용해 이제 previous 노드와 previous 노드의 next 노드 정보를 알게되었고 previous 노드의 next는 이제 current의 next가 되었고 previous 노드의 next는 current가 되었다.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor(){
this.head = null;
this.length = 0;
}
/* search 부분 */
getAt(index) {
// #1
let current = this.head;
let count = 0;
// #2
while (current) {
if (count == index) {
console.log(`${index}번째 노드의 값: ${current.data}`);
}
count++;
current = current.next;
}
return null;
}
}
↑ 노드 찾기 getAt
#1 - linked list에서는 뭐든지 head 부터 시작한다.
#2 - 반복문으로 head 부터 순차적으로 사용자가 입력한 위치의 노드를 찾는다.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor(){
this.head = null;
this.length = 0;
}
/* remove 부분 */
removeAt(index) {
// #1
if (index > 0 && index > this.length) {
return;
}
let current = this.head;
let previous;
let count = 0;
// #2
if (index === 0) {
this.head = current.next;
} else {
// #3
while (count < index) {
count++;
previous = current;
current = current.next;
}
previous.next = current.next;
}
this.length--;
}
}
↑ 중간 노드 삭제 removeAt
#1 - inset와 마찬기지로 사용자가 잘못된 위치를 입력하면 메서드는 작동되지 않고 return 된다.
#2 - 만약 index가 0이라면 head의 next 가 head가 된다.
#3 - insertAt과 같은 방법으로 사용자가 입력한 위치를 반복문에 의해 list를 앞에서 부터 순차적으로 검색해 previous의 next를 current의 next로 덮어쓰면서 삭제가된 것 처럼된다.
참고링크
댓글