연결 리스트 - LinkedList
데이터를 링크로 연결해서 관리하는 자료구조를 뜻한다. 즉 데이터를 링크로 관리한다는 것은 한 줄로 연결되어 있는 방식을 의미한다고 볼 수 있다.
링크로 관리한다는 것은 무엇일까?
각 데이터의 공간마다 다음 노드를 가르키는 즉 다음 데이터 공간을 가르키는 포인터가 존재한다. 해당 포인터를 통해서 각 데이터를 한줄로 연결지어서 링크형태를 띄는데 이러한 링크형태의 자료구조중 하나를 연결리스트라고 한다.
각각 Data , next가 한쌍으로 이루어진 데이터라고 보자 해당 내용에는 data와 next가 주어지는데 해당 next가 다음 데이터를 가르키는 포인터의 역할을 한다. 즉 해당 포인터를 통해 데이터가 관리가 가능하다.
그리고 이러한 Data, Next의 한쌍을 Node라고 불리고 있다. 그렇다면 나는 나중에 추가 삭제 연산을 위한 작업 또한 할거기 때문에 미리 Node라는 형태를 코드로 나타내면 아래와 같은 코드가 된다.
class Node {
int data;
Node next;
Node() {}
Node(int data, Node next) {
this.data = data;
this.next = next;
}
}#### 그렇다면 이렇게 해서 연결리스트를 구성해서 장점은 무엇일까? >데이터의 공간을 미리 할당할 필요가 없다.
만약 데이터를 추가하고자 할때는 해당하는 공간에 할당을 링크와 함께 잘 연결지으면 되기 때문이다.
이러한 말은 리스트의 길이가 가변적이라 데이터 추가/삭제가 용이하다.
단점도 알아보자!
연결구조를 위한 별도 데이터 공간필요
연결 정보를 찾는데 시간이 필요하다.(접근 속도가 상대적으로 느림)
데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재공하는 작업이 필요
그렇다면 기본적으로 우리는 연결 리스트의 기본적인 개념을 숙지한 상태이지만 아직 미숙한 부분이 너무 많다. 위와 같은 데이터가 이루어지고 있다는것은 알았지만 아직은 미숙하다. 그렇기에 아래에서 데이터를 추가하면서 좀 더 세부적으로 알아가 보고자 한다.
데이터 추가
먼저 첫 번째로 추가가 있다. 데이터 추가에는 추가 위치에 따른 연결 작업이 필요로 한다.
먼저 data1 , data2가 위와 같은 그림으로 연결지어져 있다고 가정하자.
해당 연결리스트에 데이터를 추가 할때는
1. 추가할 데이터를 담을 노드를 생성
2. 링크 연결 작업
3. head 이전 작업
순서를 지켜줘야 한다. 참고로 위 방식은 데이터를 가장 앞에 추가할 경우를 가정하겠다.
순서를 지켰을시 아래와 같은 형태가 된다.
그렇다면 가장 끝에는 어떻게 만들까?
끝에 추가시
1. 추가할 데이터를 담을 노드를 생성
2. head로 부터 끝 노드까지 순회
3. 링크 연결 작업
하지만 역시나 말로만 하는것은 항상 그렇지만 성에차지 못하는거 같다. 코드로는 어떻게 될까?
class LinkedList {
Node head; // 최상단 노드
LinkedList() {}
LinkedList(Node node) {
this.head = node;
}
// 연결 리스트의 맨 뒤에 데이터 추가
public void addData(int data) {
if (this.head == null) {
this.head = new Node(data, null);
} else {
Node cur = this.head;
while (cur.next != null) { // 2 번방식
cur = cur.next;
}
// 다음 노드가 없을 때까지 돌았다면 현재 노드의 다음이 내가 추가할 곳이 되겠다.
cur.next = new Node(data, null); // 1 , 3 방식
}
}
}위에서는 node라는 class를 만든것을 토대로 LinkedList를 구현해봤다. 먼저 LinkedList에는 최상단 노드가 필요로 하다. 이는 head를 의미하면 항상 첫 번째에 오는 값이라고 생각하면 편하다.
위에서도 주석처리를 했지만 다시 설명을 하자면
1. addData 메소드를 실행한다면 먼저 첫 번째로 해당 head가 null인지를 체크하고 없다면 최소 노드를 생성한다.
2. 그다음으로 값이 추가가 된다면 while문을 통해 끝 노드까지 이동하여
3. 해당 노드에 포인터에 다음 노드를 가르키면서 거기에 값을 추가하면 끝이난다.
위에서 처음 , 끝에 데이터를 추가하는 방법을 알아봤는데. 이제는 중간에 값을 추가할 경우를 눈여겨 봐야할 시간이다.
다시 처음 이미지를 가져오면 data1 , data2 가 연결 리스트로 연결이 되어 있다. 나는 이 중간에 값을 넣고자 한다. 그렇다면 해당 연결리스트 포인터를 끊고 새로운 노드에 추가하면 되는 간단하면서도 어려울 거 같은 생각이 든다.
그렇다면 이론적인 순서는 어떻게 될까?
1. 추가할 데이터를 담을 노드를 생성
2. head로부터 데이터 추가 위치 직전 노드까지 순회
3. 링크 연결 작업
그렇다면 아래와 같은 형태를 가지게 된다. 바로 코드로 알아보자!!
// 연결 리스트에 데이터 추가
// before_data 가 null 인 경우, 가장 뒤에 추가
// before_data 에 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
public void addData(int data, Integer beforeData) {
if (this.head == null) {
this.head = new Node(data, null);
} else if (beforeData == null) {
Node cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = new Node(data, null);
} else {
Node cur = this.head; // 현재 데이터
Node pre = cur; // 이전 데이터
while (cur != null) {
if (cur.data == beforeData) {
if (cur == this.head) {
this.head = new Node(data, this.head);
} else {
pre.next = new Node(data, cur);
}
break;
}
pre = cur;
cur = cur.next;
}
}
}지금은 기존 코드를 리펙토링해서 새로운 매개변수를 추가하고 해당 매개변수 자리에 값을 추가하는 방식 넣은 상태이다. 우리가 눈여겨봐야 할 부분이 바로 이전 데이터를 삽입하는 부분이다.
그렇다면 위와 같은 코드를 설명으로 풀어보도록 하자.
1. 현재의 데이터와 이전데이터를 선언한다.(pre,cur) 이전 노드와 다음 노드에 삽입하기 위함이다.
2. 값을 next 하면서 현재의 데이터와 beforData와 같다면
3. 여기서 두가지로 나뉘다. 그게 head라면 다음 노드를 head로 가르키고 data를 넣으면 된다.
4. head가 아니라면 pre에 next에 새로운 노드를 생성하고 그 데이터를 담고 그 다음 노드를 cur로 해주면 데이터 삽입이 끝난다.
이렇게 기본적인 node를 LinkedList 형태를 통해 삽입하는 형식을 공부해봤는데 다른 다 자료구조랑은 다르게 어렵다...ㅠㅠ 그 밖에 원형 연결 리스트 등등 다양한 방식이 있는데 오늘은 LinkedList를 공부하면서 단방향 구조를 학습해 봤다. 실제로 필자는 코딩테스트도 열심히 준비중에 있다. 근데 이러한 LinkedList의 응용을 통해 문제를 푸는 경우가 좀 많은 거 같다. 그렇기에 오늘 학습은 좀 더 가치 있는 일이지 않았나 싶다. 그렇기에 오늘은 좀 더 재밌는거 같기도 하다.ㅋㅋㅋ
