이중 연결 리스트?
각 노드에서 양방향(선행, 후행)으로 연결되는 리스트
양 방향 접근이 용이
BUT 메모리를 추가적으로 사용
구현해 볼 메서드는?
1. 초기화
2. 리스트 맨 앞에 데이터 삽입하기
3. 리스트 맨 끝에 데이터 삽입하기
4. 리스트 중간에 원하는 자리에 데이터 삽입하기
5. 리스트에서 지우고 싶은 데이터 삭제하기
6. 리스트에서 값으로 조회해서 인덱스 번호 넘기기
7. 리스트 찾기
8. 역으로 리스트 찾기
1. 초기화
public void init() {
head = null;
tail = null;
nodeCnt = 0;
}이렇게 초기화 시켜두면 더미 노드로 처음 값을 넣을 때 값이 있나 없나 확인하고 하는 과정이 줄어든다.
2. 리스트 맨 앞에 데이터 삽입하기
public void addNode2Head(int data) {
Node newNode = getNode(data);
// 뉴노드 -> 현재 헤드로 가게 설정 / 헤드에 이전 값 뉴노드로
newNode.next = head;
// 첫 입력이면 head도 바꾸기
if (head == null) {
tail = newNode;
head = newNode;
} else {
head.prev = newNode;
head = newNode;
}
}양방향 연결 리스트이므로 원래 맨 앞이던 head 노드를 새로 생성한 newNode에 next를 가르키도록 변경하고 이전을 가리키는 prev를 새로 생성한 newNode로 지정해준다.
3. 리스트 맨 끝에 데이터 삽입하기
public void addNode2Tail(int data) {
Node newNode = getNode(data);
newNode.prev = tail;
// 테일에다가 넣기
if (tail == null) {
tail = newNode;
head = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
}이번엔 끝에 추가하니까 tail 값이 newNode.prev가 가리키도록 설정
4. 리스트 중간에 원하는 자리에 데이터 삽입하기
public void addNode2Num(int data, int num) {
if (num < 0 || num > nodeCnt + 1) {
throw new IndexOutOfBoundsException();
}
// 위치를 찾았고
if (num == 1) {
addNode2Head(data);
} else {
Node cur = head;
for (int i = 1; i < num - 1; i++) {
cur = cur.next;
}
// 만약 넣는 곳이 끝이면
if (cur.next == null) {
addNode2Tail(data);
} else {
// 아니면 중간 연결 끊고 새로 이어주기
Node newNode = getNode(data);
Node next = cur.next;
cur.next = newNode;
next.prev = newNode;
newNode.prev = cur;
newNode.next = next;
}
}
}num이 1이면 맨 앞에 넣는 것이라 addNode2Head 메소드 호출
head부터 시작해서 num 값 만큼 노드를 타고 넘어가서 node를 찾는다.
찾은 node에 next가 null이면 제일 끝 값이니까 addNode2Tail 메소드 호출
모두 아니면 중간에 삽입하면서 연결을 끊고 새로운 노드와 연결 시켜준다.
위 그림과 같이 동작
5. 리스트에서 지우고 싶은 데이터 삭제하기
public void removeNode(int data) {
if (head == null) return;
if (head.data == data) {
head = head.next;
if (head == null) {
tail = null;
}
nodeCnt--;
}
Node cur = head;
while (cur != null && cur.data != data) {
cur = cur.next;
}
/// 값인 애는 찾음
// 다음 값이
if (cur != null && cur.data == data) {
// 제거할 노드가 마지막일 경우
if (cur == tail) {
tail = cur.prev;
}
cur.prev.next = cur.next;
nodeCnt--;
}
}이번엔 지난 게시글인 단순 연결 리스트와 다르게 data 값이 제일 처음 나온 인덱스만 삭제하도록 구현하였다.
6. 리스트에서 값으로 조회해서 인덱스 번호 넘기기
public int findNode(int data) {
Node cur = head;
int res = 1;
while (cur.next != null && cur.data != data) {
res++;
cur = cur.next;
}
return res;
}data 값이 같은 Node를 찾을 때까지 현재 노드를 다음 노드로 이동시키면서 값을 확인한다.
7. 리스트 찾기
public int getList(int[] output) {
Node cur = head;
for (int i = 0; i < nodeCnt; i++) {
output[i] = cur.data;
cur = cur.next;
}
return nodeCnt;
}현재 링크드 리스트에 저장된 값을 찾아서 보내주기 위한 함수다.
8. 역으로 리스트 찾기
public int getReversedList(int[] output) {
Node cur = tail;
for (int i = 0; i < nodeCnt; i++) {
output[i] = cur.data;
cur = cur.prev;
}
return nodeCnt;
}위와 같지만 tail부터 시작해서 반대로 값을 리턴하기 위한 함수이다.
양방향 링크드 리스트이기 때문에 쉽게 가능!
전체 코드
class Node {
public int data;
public Node prev;
public Node next;
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", next=" + next +
'}';
}
}
public class UserSolution {
private final static int MAX_NODE = 10000;
private Node[] node = new Node[MAX_NODE];
private int nodeCnt = 0;
private Node head, tail;
public Node getNode(int data) {
node[nodeCnt] = new Node(data);
return node[nodeCnt++];
}
public void init() {
head = null;
tail = null;
nodeCnt = 0;
}
public void addNode2Head(int data) {
Node newNode = getNode(data);
// 뉴노드 -> 현재 헤드로 가게 설정 / 헤드에 이전 값 뉴노드로
newNode.next = head;
// 첫 입력이면 head도 바꾸기
if (head == null) {
tail = newNode;
head = newNode;
} else {
head.prev = newNode;
head = newNode;
}
}
public void addNode2Tail(int data) {
Node newNode = getNode(data);
newNode.prev = tail;
// 테일에다가 넣기
if (tail == null) {
tail = newNode;
head = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
}
public void addNode2Num(int data, int num) {
if (num < 0 || num > nodeCnt + 1) {
throw new IndexOutOfBoundsException();
}
// 위치를 찾았고
if (num == 1) {
addNode2Head(data);
} else {
Node cur = head;
for (int i = 1; i < num - 1; i++) {
cur = cur.next;
}
// 만약 넣는 곳이 끝이면
if (cur.next == null) {
addNode2Tail(data);
} else {
// 아니면 중간 연결 끊고 새로 이어주기
Node newNode = getNode(data);
Node next = cur.next;
cur.next = newNode;
next.prev = newNode;
newNode.prev = cur;
newNode.next = next;
}
}
}
public int findNode(int data) {
Node cur = head;
int res = 1;
while (cur.next != null && cur.data != data) {
res++;
cur = cur.next;
}
return res;
}
public void removeNode(int data) {
if (head == null) return;
if (head.data == data) {
head = head.next;
if (head == null) {
tail = null;
}
nodeCnt--;
}
Node cur = head;
while (cur != null && cur.data != data) {
cur = cur.next;
}
/// 값인 애는 찾음
// 다음 값이
if (cur != null && cur.data == data) {
// 제거할 노드가 마지막일 경우
if (cur == tail) {
tail = cur.prev;
}
cur.prev.next = cur.next;
nodeCnt--;
}
}
public int getList(int[] output) {
Node cur = head;
for (int i = 0; i < nodeCnt; i++) {
output[i] = cur.data;
cur = cur.next;
}
return nodeCnt;
}
public int getReversedList(int[] output) {
Node cur = tail;
for (int i = 0; i < nodeCnt; i++) {
output[i] = cur.data;
cur = cur.prev;
}
return nodeCnt;
}
}이제 링크드 리스트를 어느정도 이해하고 필요에 따라서 수정된 링크드 리스트를 이용할 수 있을 것 같다.
'Computer Science > 자료구조' 카테고리의 다른 글
| [JAVA] 단순 연결 리스트 (Singly Linked List) 구현 (0) | 2023.07.21 |
|---|