Linked List란?
리스트 자료구조는 데이터를 나란히 저장한다.
Linked List란 각각의 Node(data)가 data와 tail을 한 쌍의 data set으로 구성되어 다음 node는 앞의 node의 tail과 연결되어 있는 형태의 자료구조다. 한마디로 데이터들의 기차놀이.
Linked List의 특징
data의 입력/삭제가 자유롭다. 새로운 데이터를 입력할 때 앞 node의 tail에 자신의 data를 연결하고 자신의 tail을 원래 자신의 앞 node tail에 연결되었던 node와 연결하면 된다. 그렇기 때문에 마지막 항목은 null이다.
노드(Node)
연결 리스트에서 각 원소는 원소 자신과 다음 원소를 가리키는 포인터가 포함된 노드로 구성된다.
연결 리스트 만들기
일단 Node와 LinkedList를 생성자 함수를 만든다. LinkedList는 자료의 전체 길이인 length가 필요하고 head가 있어야 한다. Node엔 data와 next가 있어야 한다. 아직 아무런 node가 없기 때문에 next와 head는 초기에 null로 해둔다. 그리고 생성자 함수에 prototype에 push를 정의한다. 인자로 데이터를 받고 생성자 함수로 부터 node를 생성한다.
이제 push를 통해 node를 추가하고 list와 node 콘솔을 찍어보자
간장게장처럼 알차게 데이터가 들어간 것을 확인할 수 있다. push를 한 번 더 하면
이렇게 무질서하게 노드가 생성됐다. 이제 헤드와 next를 정해줘야 한다. 일단 curr이란 변수를 선언한다.
만약 head가 null이면 즉, 배열에 아무것도 없다면 this.head에 node 즉, 지금 들어온 데이터를 할당한다.
이제 list에 head가 생겼다. 이제 next를 해주장
curr란 임시 변수에 this.head즉, 기존의 node를 담고 기존의 노드에 프로퍼티인 next에 지금 들어온 노드를 할당한다. 그럼 1번 노드의 next가 2번 노드를 가리킨다.
매우 아름답다..
이제 문제는 다음 데이터들을 추가했을 때다. 3이란 숫자를 푸시하면
1번 노드가 새로 들어온 노드를 가리킨다. 즉, 순차적으로 노드가 가리키게 해야 한다. 그러면 일단 while이고 조건은 .next가 있을 때다. next가 있으면 새로 들어온 데이터를 방금 전에 새로 들어온 데이터에 달아줘야 한다.
즉, 13학번이 들어오면 11학번이 아닌 12학번 뒤에 세워야 하는 것.
더욱 아름다워졌다. 이제 push가 될 때마다 length를 늘여서 전체 list를 커지게 하면 된다.
참고 :
