단순 연결리스트?
각 노드에서 단방향으로 연결되는 리스트
후행 노드로는 쉽게 접근 가능
BUT 선행 노드 접근이 복잡한 단점 존재
구현해 볼 메서드는?
1. 초기화
2. 리스트 맨 앞에 데이터 삽입하기
3. 리스트 맨 끝에 데이터 삽입하기
4. 리스트 중간에 원하는 자리에 데이터 삽입하기
5. 리스트에서 지우고 싶은 데이터 삭제하기
6. 리스트에서 인덱스 번호를 받아서 데이터 찾기
구현
구현은 정적 할당을 통한 메모리 풀 방식으로 구현할 것입니다.
당연히 평소엔 동적 할당을 통해서 사용해야겠지만 알고리즘 문제를 풀 때는 동적 할당을 하면 성능 문제로 정적으로 할당합니다.
=> 모든 노드가 메모리 상에서 뭉쳐 있어 캐시 효율 증가
0. 노드 생성
public Node getNode(int data) {
node[nodeCnt] = new Node(data);
return node[nodeCnt++];
}
1. 초기화
알고리즘을 풀면서 단순 연결리스트를 직접 구현한다면 테스트 케이스마다 초기화를 시켜줘야 해서 구현하는 메서드
public void init() {
head = null;
tail = null;
nodeCnt = 0;
}간단하게 시작 노드를 나타내는 head와 끝 노드를 나타내는 tail 그리고 현재까지 들어왔던 노드 개수만 초기화시키면 된다.
2. 리스트 맨 앞에 데이터 삽입하기
// 맨 앞에 노드 추가
public void addNode2Head(int data) {
// 데이터를 가진 노드를 하나 추가해주고
Node newNode = getNode(data);
newNode.next = head;
// 이전에 아무것도 없는 빈 상태면 테일 값 추가
if (head == null) {
tail = newNode;
}
head = newNode;
}새로운 노드를 생성하고 현재 헤드 노드를 새로 생성한 노드에 next 값으로 담아 방향을 설정한다.
삽입 전
head -> data -> data
삽입 후
newNode -> head -> data -> data
newNode를 헤드로 변경
head -> data(head였던) -> data -> data
3. 리스트 맨 끝에 데이터 삽입하기
public void addNode2Tail(int data) {
Node newNode = getNode(data);
// 만약 리스트가 빈 상태
if (head == null) {
head = newNode;
tail = newNode;
}
else {
tail.next = newNode;
tail = newNode;
}
}위 헤드에 삽입과 거의 비슷하다.
새로운 노드를 생성하고 이전 tail이 null을 next로 갖고 있었을 텐데 이제 next로 newNode를 갖는다.
4. 리스트 중간에 원하는 자리에 데이터 삽입하기
public void addNode2Num(int data, int num) {
if (num < 0 || num > nodeCnt + 1) {
throw new IndexOutOfBoundsException();
}
Node newNode = getNode(data); // 새로 넣은 노드를 생성해둔다.
if (num == 1) {
newNode.next = head;
head = newNode;
if (tail == null) {
tail = newNode;
}
} else {
// 이제 저 위치까지 탐색하면서 넣은 노드를 찾는다.
Node nextNode = head;
for (int i = 1; i < num - 1; i++) {
nextNode = nextNode.next;
}
if (nextNode.next == null) {
nextNode.next = newNode;
tail = newNode;
}else {
newNode.next = nextNode.next;
nextNode.next = newNode;
}
}
}인덱스 번호 num을 받아서 해당 위치에 새로운 data를 넣는다.
인덱스 번호 num이 1부터 들어오는 값을 받아서 num - 1까지 리스트를 순회하면서 들어갈 node 위치가 어디인지 찾는다.
num이 1이 들어오면 맨 앞에 넣는다.
그게 아니면 찾은 num위치에서 다음이 비어있다면 맨 끝에 노드를 추가한다는 의미로 tail도 변경하고 next로 newNode를 넣으며 노드 연결
끝 값이 아니면 찾은 노드가 갖고 있던 next값을 newNode에 다음 값으로 추가하고 newNode를 next에 넣으면서 노드를 연결시켜 준다.
연결 전
nextNode -> data
연결 후
nextNode -> newNode -> data
5. 리스트에서 지우고 싶은 데이터 삭제하기
public void removeNode(int data) {
while (head != null && head.data == data) {
// head 노드가 삭제 대상인 경우
head = head.next;
nodeCnt--;
}
if (head != null) {
Node prevNode = head;
while (prevNode.next != null) {
if (prevNode.next.data == data) {
// 삭제 대상 노드를 찾은 경우
if (prevNode.next == tail) {
tail = prevNode;
}
prevNode.next = prevNode.next.next;
nodeCnt--;
} else {
// 삭제 대상 노드가 아닌 경우 다음 노드로 이동
prevNode = prevNode.next;
}
}
}
}지우고 싶은 data 값을 갖는 노드를 전부 찾아 지우는 메서드로 구현해 보았다.
자바에서 구현된 링크드 리스트는 제일 처음 찾은 데이터만 지우는데 이렇게 메서드를 작성하면 모든 데이터를 순회하니까 O(n)이 필요하다.
하지만 같은 값이 여러 개라면 이런 식으로 구현하면 시간복잡도를 줄일 수도 있다.
이런 식으로 내가 원하는 방식으로 자료구조를 수정할 수 있게 하는 게 현재 공부 목표이기도 하다.
6. 리스트에서 인덱스 번호를 받아서 데이터 찾기
public Node search (int index) {
if (index < 0 || index >= MAX_NODE) {
throw new IndexOutOfBoundsException();
}
Node x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}원하는 인덱스까지 리스트를 순회하면서 값을 찾아 리턴해준다.
전체 코드
class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
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;
// data 값을 갖는 노드를 생성하고 생성된 node를 리턴
public Node getNode(int data) {
node[nodeCnt] = new Node(data);
return node[nodeCnt++];
}
// init 메소드를 통해 헤드를 초기화 시키고 node 값을 0으로 초기화
public void init() {
head = null;
tail = null;
nodeCnt = 0;
}
// 맨 앞에 노드 추가
public void addNode2Head(int data) {
// 데이터를 가진 노드를 하나 추가해주고
Node newNode = getNode(data);
newNode.next = head;
// 이전에 아무것도 없는 빈 상태면 테일 값 추가
if (head == null) {
tail = newNode;
}
head = newNode;
}
// 맨 끝에 노드 추가
public void addNode2Tail(int data) {
Node newNode = getNode(data);
// 만약 리스트가 빈 상태
if (head == null) {
head = newNode;
tail = newNode;
}
else {
tail.next = newNode;
tail = newNode;
}
}
// 지정된 num에 노드 추가
public void addNode2Num(int data, int num) {
if (num < 0 || num > nodeCnt + 1) {
throw new IndexOutOfBoundsException();
}
Node newNode = getNode(data); // 새로 넣은 노드를 생성해둔다.
if (num == 1) {
newNode.next = head;
head = newNode;
if (tail == null) {
tail = newNode;
}
} else {
// 이제 저 위치까지 탐색하면서 넣은 노드를 찾는다.
Node nextNode = head;
for (int i = 1; i < num - 1; i++) {
nextNode = nextNode.next;
}
if (nextNode.next == null) {
nextNode.next = newNode;
tail = newNode;
}else {
newNode.next = nextNode.next;
nextNode.next = newNode;
}
}
}
public void removeNode(int data) {
while (head != null && head.data == data) {
// head 노드가 삭제 대상인 경우
head = head.next;
nodeCnt--;
}
if (head != null) {
Node prevNode = head;
while (prevNode.next != null) {
if (prevNode.next.data == data) {
// 삭제 대상 노드를 찾은 경우
if (prevNode.next == tail) {
tail = prevNode;
}
prevNode.next = prevNode.next.next;
nodeCnt--;
} else {
// 삭제 대상 노드가 아닌 경우 다음 노드로 이동
prevNode = prevNode.next;
}
}
}
}
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 Node search (int index) {
if (index < 0 || index >= MAX_NODE) {
throw new IndexOutOfBoundsException();
}
Node x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
}'Computer Science > 자료구조' 카테고리의 다른 글
| [JAVA] 이중 연결 리스트 (Doubly Linked List) 구현 (0) | 2023.07.25 |
|---|