Java에서 일반 LinkedList 만들기
Suraj P
2023년10월12일
이 기사에서는 Java에서 일반 singly LinkedList를 작성하는 방법을 알려줍니다.
Java의 LinkedList에 대한 간략한 소개
‘LinkedLists’는 임의의 주소에 있는 노드에 데이터를 저장하고 인접하지 않은 위치에 있는 수단을 의미하는 선형 데이터 구조입니다.
모든 노드에는 데이터와 참조(주소)의 두 부분이 있습니다. Data/value 필드는 값을 저장하고 reference 필드는 연결 목록의 다음 노드 주소를 저장합니다.
멤버 함수로 구현될 이 데이터 구조의 일반적인 작업 중 일부는 다음과 같습니다.
addNode()- 이 메서드는LinkedList끝에 새 요소를 추가하는 데 사용됩니다.removeNode(value)- 이 메서드는 지정된 값을 가진 노드를 제거합니다.addNode(position,value)- 이 메서드는 특정 위치에 값을 추가하는 데 사용됩니다.clear()- 이 메서드는 전체LinkedList를 지웁니다.isEmpty()- 이 메소드는LinkedList가 비어 있는지 여부를 확인하는 데 사용됩니다.length()- 이 메서드는LinkedList의 길이를 제공합니다.
Java에서 단일 LinkedList의 일반 구현
일반 LinkedList는 정수, 문자열, 부울, 부동 등 한 가지 유형의 값만 저장할 수 있습니다. 따라서 생성 시 유형을 지정해야 하지만 LinkedList를 생성하려면 어떻게 해야 합니까? 모든 데이터 유형의 데이터를 저장합니다. 이를 위해 Java에서 제네릭 개념을 사용합니다.
일반 노드 클래스 만들기:
아래 코드에서 T는 LinkedList에 저장된 데이터의 유형을 나타냅니다.
class Node<T> {
T value;
Node<T> nextPtr;
Node(T value) {
this.value = value;
this.nextPtr = null;
}
}
이제 일반적인 LinkedList 클래스 생성 메서드를 생성해 보겠습니다.
-
추가()기능:void add(T value) { Node<T> temp = new Node<>(value); // creating a new node if (this.head == null) // checking if the list is empty head = temp; else // if the list is not empty, we go till the end and add the node { Node<T> tr = head; while (tr.nextPtr != null) { tr = tr.nextPtr; } tr.nextPtr = temp; } length = length + 1; // increasing the length of list } -
제거()기능:void remove(T key) { Node<T> prev = new Node<>(null); prev.nextPtr = head; Node<T> next = head.nextPtr; Node<T> tr = head; boolean isNodepresent = false; // to check if node is present if (head.value == key) { head = head.nextPtr; isNodepresent = true; } while (tr.nextPtr != null) { if (String.valueOf(tr.value).equals( String.valueOf(key))) { // if the node is present, we break the loop prev.nextPtr = next; // we assign previous node's nextPtr to next node isNodepresent = true; break; } prev = tr; // updating the previous and next pointers tr = tr.nextPtr; next = tr.nextPtr; } if (isNodepresent == false && String.valueOf(tr.value).equals(String.valueOf(key))) { prev.nextPtr = null; isNodepresent = true; } if (isNodepresent) { length--; // if the node is present, we reduce the length } else { System.out.println("The value is not present inside the LinkedList"); } } -
추가(위치,값)기능:void add(int position, T value) { if (position > length + 1) // if the position entered is more than the list length { System.out.println("Position out of bound"); return; } if (position == 1) { // if the position is one we'll just Node<T> temp = head; head = new Node<T>(value); head.nextPtr = temp; return; } Node<T> tr = head; Node<T> prev = new Node<T>(null); // creating a new node prev while (position - 1 > 0) // we find the position in the list { prev = tr; tr = tr.nextPtr; position--; } prev.nextPtr = new Node<T>(value); // update the next pointer of previous node prev.nextPtr.nextPtr = tr; } -
getLength()함수:int getLength() { return this.length; // returns the length of the list } -
isEmpty()함수:boolean isEmpty() { if (head == null) // if the list is empty we return true return true; else return false; } -
clear()함수:void clear() { head = null; // make head as null and length as zero length = 0; } -
toString()함수:아래 코드에서
LinkedList의 내용을 인쇄하기 위해toString메서드를 추가하고 재정의했습니다.@Override public String toString() { Node<T> temp = head; String str = "{ "; if (temp == null) // if the list is empty { System.out.println("list is empty"); } while (temp.nextPtr != null) // we keep appending data to string till the list is empty { str += String.valueOf(temp.value) + "->"; temp = temp.nextPtr; } str += String.valueOf(temp.value); return str + "}"; // we finally return the string }
main 클래스의 전체 작업 코드:
class Node<T> {
T value;
Node<T> nextPtr;
Node(T value) {
this.value = value;
this.nextPtr = null;
}
}
class LinkedList<T>
{
Node<T> head;
private int length = 0;
LinkedList()
{
this.head = null;
}
void add(T value)
{
Node<T> temp = new Node<>(value);
if(this.head == null)
head = temp;
else
{
Node<T> tr = head;
while(tr.nextPtr!=null){
tr = tr.nextPtr;
}
tr.nextPtr = temp;
}
length = length + 1;
}
void remove(T key)
{
Node<T> prev = new Node<>(null);
prev.nextPtr = head;
Node<T> next = head.nextPtr;
Node<T> tr = head;
boolean isNodepresent = false;
if(head.value == key ){
head = head.nextPtr;
isNodepresent =true;
}
while(tr.nextPtr!=null)
{
if(String.valueOf(tr.value).equals(String.valueOf(key))){
prev.nextPtr = next;
isNodepresent = true;
break;
}
prev = tr;
tr = tr.nextPtr;
next = tr.nextPtr;
}
if(isNodepresent==false && String.valueOf(tr.value).equals(String.valueOf(key))){
prev.nextPtr = null;
isNodepresent = true;
}
if(isNodepresent)
{
length--;
}
else
{
System.out.println("The value is not present inside the LinkedList");
}
}
void add(int position,T value)
{
if(position>length+1)
{
System.out.println("Position out of bound");
return;
}
if(position==1){
Node<T> temp = head;
head = new Node<T>(value);
head.nextPtr = temp;
return;
}
Node<T> tr = head;
Node<T> prev = new Node<T>(null);
while(position-1>0)
{
prev = tr;
tr = tr.nextPtr;
position--;
}
prev.nextPtr = new Node<T>(value);
prev.nextPtr.nextPtr = tr;
}
int getLength()
{
return this.length;
}
boolean isEmpty()
{
if(head == null)
return true;
else
return false;
}
void clear()
{
head = null;
length = 0;
}
@Override
public String toString()
{
Node<T> temp = head;
String str = "{ ";
if(temp == null)
{
System.out.println( "list is empty");
}
while(temp.nextPtr!=null)
{
str += String.valueOf(temp.value) +"->";
temp = temp.nextPtr;
}
str += String.valueOf(temp.value);
return str+"}";
}
}
public class Example
{
public static void main(String[] args) {
LinkedList<Integer> ll = new LinkedList<>();
ll.add(1);
ll.add(2);
ll.add(3);
System.out.println(ll);
ll.remove(3);
System.out.println(ll);
ll.add(2,800);
System.out.println(ll);
}
}
출력:
{ 1->2->3}
{ 1->2}
{ 1->800->2}
작가: Suraj P
