연결 리스트에는 단순, 원형, 이중 연결리스트 등이 존재합니다. 오늘은 이 중 첫 번째인 단순 연결 리스트를 구현해보도록 하겠습니다.
1. 노드 생성
우선 제일 먼저 할 일은 노드를 생성하는 부분을 구현하는 것 입니다. 지난 포스트에서 소개한 노드의 구조를 보면 다음과 같이 데이터와 링크 필드 두가지로 구현되어 있습니다.
public class LinkedList {
private class Node {
//노드
private Object data; //데이터 필드
private Node next; //링크 필드
public Node(Object input) {
this.data = input;
this.next = null;
}
}
//첫 번째 노드
private Node head;
//마지막 노드
private Node tail;
//리스트의 크기 = 노드 갯수
private int sizeOfList = 0;
}class Node에서 노드를 생성하고 데이터를 담습니다. 그 이후에 오는 private 변수 세 개는 리스트 구현에서 활용될 LinkedList 클래스의 멤버변수들 입니다.
2. 노드 삽입
2-1. 리스트의 처음에 노드 삽입하기
우선 리스트의 첫 부분(머리)에 노드를 삽입하는 메서드입니다.
public void insertFirst(Object input) {
Node newNode = new Node(input);
//기존 head 노드를 새 노드의 다음으로 지정
newNode.next = head;
//head를 새로 생성한 노드로 지정
head = newNode;
sizeOfList++;
if(head.next == null) {
//1칸 짜리 리스트면 head는 tail이 된다.
tail = head;
}
}
2-2. 리스트의 중간에 노드 삽입하기
리스트의 중간 부분에 노드를 삽입하는 것은 처음이나 끝부분에 비해서 살짝 추가적인 과정을 요구합니다.
public Node node(int idx) {
Node n = head;
for (int i = 0; i < idx; i++) {
n = n.next;
}
return n;
}
public void insert(int idx, Object input) {
if (idx == 0) {
insertFirst(input);
}
else {
Node temp1 = node(idx - 1);
Node temp2 = temp1.next;
Node newNode = new Node(input);
temp1.next = newNode;
newNode.next = temp2;
sizeOfList++;
if (newNode.next == null) {
tail = newNode;
}
}
}
살짝 뜯어보기로 합시다.
public Node node(int idx) {
Node n = head;
for (int i = 0; i < idx; i++) {
//idx위치까지의 노드를 n에 덮어씌우며 저장
n = n.next;
}
//idx위치의 노드 n을 반환
return n;
}
이 부분은 리스트에서 특정 노드의 위치를 찾는 메소드입니다. 중간에 삽입하기 위해서는 이전의 노드를 찾아야겠죠. 사용자로부터 원하는 위치(idx)를 입력받으면 그 위치까지 for문을 통해 찾아갑니다.
public void insert(int idx, Object input) {
//idx가 0, 리스트가 비어있으면 머리에 삽입
if (idx == 0) {
insertFirst(input);
}
else {
//이전 노드를 저장할 임시 변수 temp1
Node temp1 = node(idx - 1);
//temp1의 링크 필드가리키는 노드를 임시로 저장할 변수 temp2
//이 노드가 idx번째의 노드
Node temp2 = temp1.next;
Node newNode = new Node(input);
//기존 노드의 링크필드를 새로 생성한 노드를 가리키도록 설정
temp1.next = newNode;
//새 노드의 링크필드가 다음 노드를 가리키도록 설정
newNode.next = temp2;
sizeOfList++;
if (newNode.next == null) {
tail = newNode;
}
}
}이 부분이 중간에 삽입하는 메소드입니다. 글보다는 그림이해가 빠르실 것 같습니다.
이처럼 이전 노드와 지정한 위치의 노드를 빼놨다가 그 사이에 새 노드를 삽입하는 작업을 마친 후 다시 이어줍니다. 이것이 연결 리스트 노드의 중간 삽입입니다.
2-3. 리스트 마지막에 노드 삽입하기
public void insertLast(Object input) {
if (sizeOfList == 0) {
insertFirst(input);
}
else {
Node newNode = new Node(input);
//기존 tail노드가 새 노드를 가리키도록 설정
tail.next = newNode;
//tail을 새로 생성한 노드를 가리키도록 설정
tail = newNode;
sizeOfList++;
}
}꼬리 부분에 삽입하는 과정은 처음과 중간 삽입에 비해서 비교적 간단합니다.
3. 노드 삭제
3-1. 리스트의 처음 노드 삭제하기
public void removeFirst() {
//head를 두 번째 노드가 차지하도록 변경
head = head.next;
sizeOfList--;
}처음 부분의 노드를 삭제하는 것은 매우 간단합니다. 그냥 두번째 노드가 head를 나타내게 하면 됩니다.
3-2. 리스트의 중간 노드 삭제하기
public void remove(int idx){
if(idx == 0) {
removeFirst();
}
else {
//삭제 이전 노드를 temp에 저장
Node temp = node(idx-1);
//현재 노드(=삭제할 노드)를 임시로 저장;
Node tempDeleteNode = temp.next;
//temp가 삭제 노드 다음을 가리키도록 설정
temp.next = temp.next.next;
//삭제 노드가 마지막였다면 temp가 tail이 됩니다.
if(tempDeleteNode == tail) {
tail = temp;
}
tempDeleteNode = null;
sizeOfList--;
}
}삽입 메소드에서 이용했던 node()메소드(특정 위치를 찾는 메소드)를 여기서 다시 한 번 사용합니다. 삭제는 간단한 것이 그냥 이전 노드(temp)가 삭제 노드의 링크 필드가 가리키는 노드를 가리키도록 하면 됩니다.
이 과정이 temp.next = temp.next.next; 문장으로 수행됩니다.
3-3. 리스트의 마지막 노드 삭제하기
public void removeLast() {
if(sizeOfList == 1){
removeFirst();
}
else {
//tail 바로 앞의 노드를 저장하는 temp변수
Node temp = node(sizeOfList - 2);
//temp의 링크 필드를 비웁니다.
temp.next = null;
//tail을 temp로 설정하면 끝
tail = temp;
sizeOfList--;
}
}마지막 부분의 삭제도 간단합니다. tail 이전의 노드를 가져와서 그 노드를 tail로 설정하기만 하면 됩니다.
4. 리스트에서 검색하기
자료구조의 주 기능인 검색입니다. 이 부분이 핵심 기능이라고도 할 수 있죠. 검색에도 여러 방식이 있겠지만 인덱스로 검색하는 방식을 다뤄보겠습니다.
public Node search(int idx){
int i = 0;
//검색 결과를 담기위한 변수 node
//head,즉 처음 노드로 초기화 저장
Node node = head;
//idx에 도달할때 까지 반복
while(i != idx) {
//노드에 다음 노드를 저장
node = node.next;
i++;
}
//while문 종료 후 node에 저장되어있는 노드 반환
return node;
}검색 하는 핵심 부분은 while문 부분입니다. i가 idx와 같지 않을 때 까지, 즉 찾는 위치의 바로전 노드 까지 반복합니다. 이러면 node에는 node.next가 저장되어 우리가 원하는 노드를 찾을 수 있습니다.
5. 전체 코드
public class LinkedList {
private class Node {
private Object data;
private Node next;
public Node(Object input) {
this.data = input;
this.next = null;
}
}
private Node head;
private Node tail;
private int sizeOfList = 0;
public void insertFirst(Object input) {
Node newNode = new Node(input);
newNode.next = head;
head = newNode;
sizeOfList++;
if (head.next == null) {
tail = head;
}
}
public Node node(int idx) {
Node n = head;
for (int i = 0; i < idx; i++) {
n = n.next;
}
return n;
}
public void insert(int idx, Object input) {
if (idx == 0) {
insertFirst(input);
}
else {
Node temp1 = node(idx - 1);
Node temp2 = temp1.next;
Node newNode = new Node(input);
temp1.next = newNode;
newNode.next = temp2;
sizeOfList++;
if (newNode.next == null) {
tail = newNode;
}
}
}
public void insertLast(Object input) {
if (sizeOfList == 0) {
insertFirst(input);
}
else {
Node newNode = new Node(input);
tail.next = newNode;
tail = newNode;
sizeOfList++;
}
}
public void removeFirst() {
head = head.next;
sizeOfList--;
}
public void remove(int idx){
if(idx == 0) {
removeFirst();
}
else {
Node temp = node(idx-1);
Node tempDeleteNode = temp.next;
temp.next = temp.next.next;
if(tempDeleteNode == tail) {
tail = temp;
}
tempDeleteNode = null;
sizeOfList--;
}
}
public void removeLast() {
if(sizeOfList == 1){
removeFirst();
}
else {
Node temp = node(sizeOfList - 2);
temp.next = null;
tail = temp;
sizeOfList--;
}
}
public Node search(int idx){
int i = 0;
Node node = head;
while(i != idx) {
node = node.next;
i++;
}
return node;
}
}참조
https://opentutorials.org/module/1335/8857
LinkedList - Java 구현 - Data Structure (자료구조)
여기서는 Java에서 LinkedList를 구현하는 방법을 알아보겠습니다. LinkedList의 사용방법은 이미 ArrayList API 시간에 살펴봤습니다. ArrayList와 LinkedList 모두 List에 대해서 구현방법만 달리한 것입니다.
opentutorials.org
연결 리스트(linked list) 자바로 구현하기
연결 리스트(Linked List) 각 노드가 서로 연결되어 있는 방식으로 데이터가 저장돼 있는 추상적 자료형이다. 각 노드는 와 로 구성되어 있다. 마지막 노드의 포인터는 NULL…
hanul-dev.netlify.app
https://freestrokes.tistory.com/84
Java로 연결 리스트(Linked List) 구현하기
Java로 연결 리스트(Linked List) 구현하기 Java로 연결 리스트(Linked List)를 구현하는 방법에 대해 알아보겠습니다. 1. 연결 리스트(Linked List) 연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄
freestrokes.tistory.com
'Programming > 자료구조' 카테고리의 다른 글
| 연결 리스트 Linked List (0) | 2021.09.03 |
|---|---|
| 자료구조 다시 시작하기 (0) | 2021.08.27 |
| [Data Structure] 연결 리스트(Linked List) (0) | 2021.06.25 |
| [Data Structure] 선형 리스트 (Linear List) (0) | 2021.06.24 |
| [Data Structure] 리스트 (List) (0) | 2021.06.24 |
댓글