[자료구조/JAVA] 연결 리스트(Linked List)
2024. 3. 13. 09:41
반응형
연결 리스트란?
동적 메모리 할당을 이용하여 구현되는 리스트 형태의 자료구조이다. 리스트는 순서가 있는 요소들의 컬렉션이며, 인덱스로 접근 가능하다
연결 리스트의 구성은 노드로 이루어져어 있으며 각 노드는 데이터를 저장하는 데이터 필드와 다른 노드를 가리키는 참조(포인터) 필드로 구성된다. 이에 따라서 연결 리스트의 특정 인덱스의 원소를 탐색하는 알고리즘으로 순차적 탐색을 사용하게 된다.(배열을 사용하지 않기 때문에 인덱스로 접근 불가능)
연결 리스트의 대표적인 종류로는 단순 연결 리스트, 이중 연결 리스트, 환형 연결 리스트가 있다.
해당 포스팅에서는 위의 세 가지 연결 리스트를 직접 구현해보고, Java Collection에서 제공하는 LinkedList 클래스와 시간 복잡도에 대해서 다룬다.
단순 연결 리스트 (Simple Linked List)
가장 기본적인 형태의 연결 리스트이다.
각 노드는 데이터 필드와, 다음 순서의 노드를 가리키는 참조 필드로 구성되며, 탐색은 첫 노드(head)부터 순차적으로 이루어지게 된다.
노드의 구성
class SimpleNode <E> {
E data;
SimpleNode<E> next;
public SimpleNode(E data){
this.data = data;
this.next = null;
}
}
데이터 필드와, 다음 순서의 노드를 가리키는 참조 필드가 있다.
리스트의 기본 구성
class MySimpleLinkedList<E>{
protected SimpleNode<E> head; // 연결 리스트의 첫 번째 노드를 가리킨다.
private int size; // 연결 리스트의 사이즈
public MySimpleLinkedList(){
this.head = null;
size = 0;
}
public boolean isEmpty(){
return size == 0;
}
public int size(){
return size;
}
@Override
public String toString() {
SimpleNode current = head;
StringBuilder sb = new StringBuilder();
while (current != null) {
if(current != head) {
sb.append("->");
}
sb.append(current.data);
current = current.next;
}
return sb.toString();
}
}
연결 리스트의 기본적인 구성이다. 필드로 연결 리스트의 첫 번째 노드에 해당하는 head와, 전체 리스트의 크기인 size를 가진다.
인스턴스 생성 시, Element가 없는 상태이므로 head는 null, size는 0으로 설정해주었다.
toString() 함수는 연결 리스트의 모든 Element들을 출력해주도록 작성해주었다.
삽입 연산 (처음, 끝)
public void addFirst(E data){
SimpleNode node = new SimpleNode(data);
node.next = this.head;
this.head = node;
this.size++;
}
public void addLast(E data){
SimpleNode node = new SimpleNode(data);
if(this.isEmpty()){
this.head = node;
}
else{
SimpleNode current = this.getIndexOfNode(this.size - 1);
current.next = node;
}
this.size++;
}
addFirst(처음에 삽입하는 경우)
- 새로운 노드를 생성하고 사이즈를 증가시킨다.
- 첫번째 노드(head)를 생성한 새로운 노드로 바꾸어준다.
- 기존 head는 새로운 노드의 next로 체이닝해준다. (만약 리스트 head가 없었다면(비어있는 상태) 새로운 노드의 next는 자동으로 null로 들어간다.)
addLast(마지막에 삽입하는 경우)
- 새로운 노드를 생성하고 사이즈를 증가시킨다.
- 기존 리스트의 마지막 노드를 탐색한다(getIndexOfNode()) -> 마지막 노드의 next를 새로운 노드로 설정한다.
- 만약 기존 head가 없었다면(비어있는 상태) -> 새로운 노드를 head로 설정한다.
특정 인덱스의 노드 탐색
private SimpleNode getIndexOfNode(int index){
SimpleNode current = head;
for(int i = 0; i < index; i++){
current = current.next;
}
return current;
}
위의 로직과 앞으로의 로직에서 사용될 특정 인덱스의 노드를 찾는 메서드이다. 이는 head부터 시작하여 next를 참조하여 해당 index까지 순차적으로 노드를 탐색하는 메서드이다.
삽입 연산 (특정 인덱스, 중간에 삽입)
만약 특정 인덱스에 새로운 노드를 탐색 하려면 다음 과정을 거쳐야 한다.
1. 새로운 노드의 next를 해당 인덱스의 이전 노드의 next로 설정
2. 이전 노드의 next를 새로운 노드로 변경
public void add(int index, E data) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났습니다.");
}
if (index == 0) {
this.addFirst(data);
}
else if (index == size){
this.addLast(data);
}
else{
SimpleNode newNode = new SimpleNode(data);
SimpleNode before = this.getIndexOfNode(index - 1);
//인덱스 이전의 노드 -> 새로운 노드 -> 인덱스 이전의 노드의 다음 노드
newNode.next = before.next;
before.next = newNode;
this.size++;
}
}
사이즈와 인덱스를 비교하여, 리스트의 처음이나 끝이라면 기존에 만들어두었던 addFirst()나 addLast()를 사용한다.
중간에 삽입하는 경우라면, 이전 노드(before)를 탐색하여, 새로운 노드(newNode)의 next를 이전 노드(before)의 next로 변경해준다. 이후에 before의 next를 새로운 노드로 설정해준다.
삭제 연산 (처음, 끝)
public void deleteFirst(){
if(this.isEmpty()){
throw new IndexOutOfBoundsException("리스트가 비어있습니다.");
}
this.head = this.head.next;
this.size--;
}
public void deleteLast(){
if(this.isEmpty()){
throw new IndexOutOfBoundsException("리스트가 비어있습니다.");
}
if(size == 1){
this.head = null;
}
else{
SimpleNode before = this.getIndexOfNode(this.size - 2);
before.next = null;
}
this.size--;
}
deleteFirst(처음 노드를 삭제하는 경우)
- 사이즈를 감소시킨다.
- head를 기존 head의 next로 재설정한다.
deleteLast(마지막 노드를 삭제하는 경우)
- 사이즈를 감소시킨다.
- 마지막 노드의 이전 노드를 탐색하여, 해당 노드의 next를 null로 재설정한다.
삭제 연산 (특정 인덱스, 중간 삭제)
만약 특정 인덱스의 노드를 삭제하려면 다음 과정을 거쳐야 한다.
1. 삭제할 노드의 이전 노드를 탐색
2. 이전 노드의 next를 삭제할 노드의 next로 설정
public void delete(int index) {
if(index < 0 || index > size - 1){
throw new IndexOutOfBoundsException("인덱스 범위를 벗어났습니다");
}
if (index == 0) {
this.deleteFirst();
}
else if (index == size - 1) {
this.deleteLast();
}
else{
SimpleNode before = this.getIndexOfNode(index - 1);
before.next = before.next.next;
this.size--;
}
}
데이터 선택 연산
public E get(int index) {
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났습니다.");
}
SimpleNode<E> node = this.getIndexOfNode(index);
return node.data;
}
특정 인덱스의 Node를 탐색하여 Data를 얻어오는 메서드이다.
단순 연결 리스트 : 전체 코드
class SimpleNode <E> {
E data;
SimpleNode<E> next;
public SimpleNode(E data){
this.data = data;
this.next = null;
}
}
class MySimpleLinkedList<E>{
protected SimpleNode<E> head; // 연결 리스트의 첫 번째 노드를 가리킨다.
private int size; // 연결 리스트의 사이즈
public MySimpleLinkedList(){
this.head = null;
size = 0;
}
public void addFirst(E data){
SimpleNode node = new SimpleNode(data);
node.next = this.head;
this.head = node;
this.size++;
}
public void addLast(E data){
SimpleNode node = new SimpleNode(data);
if(this.isEmpty()){
this.head = node;
}
else{
SimpleNode current = this.getIndexOfNode(this.size - 1);
current.next = node;
}
this.size++;
}
// 특정 인덱스에 요소 추가
public void add(int index, E data) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났습니다.");
}
if (index == 0) {
this.addFirst(data);
}
else if (index == size){
this.addLast(data);
}
else{
SimpleNode newNode = new SimpleNode(data);
SimpleNode before = this.getIndexOfNode(index - 1);
//인덱스 이전의 노드 -> 새로운 노드 -> 인덱스 이전의 노드의 다음 노드
newNode.next = before.next;
before.next = newNode;
this.size++;
}
}
public void deleteFirst(){
if(this.isEmpty()){
throw new IndexOutOfBoundsException("리스트가 비어있습니다.");
}
this.head = this.head.next;
this.size--;
}
public void deleteLast(){
if(this.isEmpty()){
throw new IndexOutOfBoundsException("리스트가 비어있습니다.");
}
if(size == 1){
this.head = null;
}
else{
SimpleNode before = this.getIndexOfNode(this.size - 2);
before.next = null;
}
this.size--;
}
// 특정 인덱스에 요소 삭제
public void delete(int index) {
if(index < 0 || index > size - 1){
throw new IndexOutOfBoundsException("인덱스 범위를 벗어났습니다");
}
if (index == 0) {
this.deleteFirst();
}
else if (index == size - 1) {
this.deleteLast();
}
else{
SimpleNode before = this.getIndexOfNode(index - 1);
before.next = before.next.next;
this.size--;
}
}
public E get(int index) {
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났습니다.");
}
SimpleNode<E> node = this.getIndexOfNode(index);
return node.data;
}
public boolean isEmpty(){
return size == 0;
}
public int size(){
return size;
}
private SimpleNode getIndexOfNode(int index){
SimpleNode current = head;
for(int i = 0; i < index; i++){
current = current.next;
}
return current;
}
@Override
public String toString() {
SimpleNode current = head;
StringBuilder sb = new StringBuilder();
while (current != null) {
if(current != head) {
sb.append("->");
}
sb.append(current.data);
current = current.next;
}
return sb.toString();
}
}
public static void main(String[] args) {
MySimpleLinkedList list = new MySimpleLinkedList();
list.add(0, 6);
list.add(1, 7);
System.out.println(list); // 6->7
list.addFirst(4);
list.addFirst(3);
list.addFirst(2);
System.out.println(list); // 2->3->4->6->7
list.addLast(8);
list.addLast(9);
list.add(0, 1);
list.add(4, 5);
System.out.println(list); // 1->2->3->4->5->6->7->8->9
list.deleteFirst();
list.deleteLast();
System.out.println(list); // 2->3->4->5->6->7->8
list.delete(1);
System.out.println(list); // 2->4->5->6->7->8
System.out.println(list.get(1)); // 4
}
이중 연결 리스트 (Doublely Linked List)
각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있는 자료구조이다. 단순 연결 리스트의 각 노드가 다음 노드를 가리키는 포인터만을 가지고 있던 것과 다르다.
양방향으로 탐색할 수 있다. 각 노드가 이전 노드와 다음 노드를 가리키므로 리스트의 앞쪽에서부터, 혹은 뒤쪽에서부터 탐색이 가능하다.
이는 단순 연결 리스트가 앞쪽에서부터만 탐색이 가능한 것과 대조적이며, 이에 따라서 삽입 혹은 삭제 시, 인덱스의 위치에 따라 효율적인 탐색이 가능하다.
다만 각 노드가 두 개의 포인터를 가지게 되므로 단순 연결 리스트에 비해서 더 많은 메모리 사용량을 가지게 된다.
노드의 구성
class DoubleNode<E> {
E data;
DoubleNode<E> next;
DoubleNode<E> prev;
public DoubleNode(E data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
각 노드는 데이터 필드와, 이전 순서와 다음 순서의 노드를 가리키는 참조 필드가 있다.
연결 리스트의 구성
class MyDoubleLinkedList<E> {
private DoubleNode<E> head;
private DoubleNode<E> tail;
private int size;
public MyDoubleLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public int size(){
return size;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
DoubleNode<E> current = head;
while (current != null) {
if (current != head) {
sb.append("-");
}
sb.append(current.data);
current = current.next;
}
return sb.toString();
}
}
탐색 연산
private DoubleNode<E> getNodeAtIndex(int index) {
// 리스트의 절반 이상에 해당하는 인덱스일 경우 뒤에서부터 탐색
if (index > size / 2) {
DoubleNode<E> current = tail;
for (int i = size - 1; i > index; i--) {
current = current.prev;
}
return current;
} else { // 리스트의 절반 이하에 해당하는 인덱스일 경우 앞에서부터 탐색
DoubleNode<E> current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current;
}
}
특정 인덱스의 노드를 찾는 메서드이다. 양방향으로 탐색할 수 있다. 이제 탐색을 인덱스의 위치에 따라서 처음부터, 혹은 끝부터 순차적으로 노드를 탐색이 가능하다. 따라서 단순 연결 리스트에 비해서 탐색 효율이 좋다.
삽입 연산
public void addFirst(E data) {
DoubleNode node = new DoubleNode(data);
if (isEmpty()) {
this.head = node;
this.tail = node;
}
else {
node.next = head;
this.head.prev = node;
this.head = node;
}
this.size++;
}
public void addLast(E data) {
DoubleNode<E> node = new DoubleNode<>(data);
if (isEmpty()) {
this.head = node;
this.tail = node;
}
else {
this.tail.next = node;
node.prev = tail;
this.tail = node;
}
size++;
}
public void add(int index, E data) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났습니다.");
}
if (index == 0) {
this.addFirst(data);
}
else if (index == size) {
this.addLast(data);
}
else {
DoubleNode<E> newNode = new DoubleNode<>(data);
DoubleNode<E> before = getNodeAtIndex(index - 1);
newNode.next = before.next;
before.next.prev = newNode;
before.next = newNode;
newNode.prev = before;
this.size++;
}
}
addFirst(처음에 삽입하는 경우)
- 새로운 노드를 생성하고 사이즈를 증가시킨다.
- 리스트가 비어있는 상태라면, head와 tail을 새로운 노드로 설정한다.
- 리스트에 기존 노드가 존재한다면(head != null), 새로운 노드의 next를 기존 head로 설정해주고, 기존 head의 prev를 새로운 노드로 변경한다. 그리고 리스트의 head를 새로운 노드로 변경한다.
addLast(마지막에 삽입하는 경우)
- 새로운 노드를 생성하고 사이즈를 증가시킨다.
- 리스트가 비어있는 상태라면, head와 tail을 새로운 노드로 설정한다.
- 리스트에 기존 노드가 존재한다면(tail != null), 새로운 노드의 prev를 기존 tail로 설정해주고, 기존 tail의 next를 새로운 노드로 변경한다. 그리고 리스트의 tail을 새로운 노드로 변경한다.
add(특정 인덱스에 삽입하는 경우)
- 새로운 노드를 생성하고 사이즈를 증가시킨다.
- 해당 인덱스의 이전 노드(before)을 탐색한다.
- 새로운 노드(newNode) : prev는 before / next는 before의 next로 설정
- 이전 노드(before) : next -> 새로운 노드(newNode)로 설정
- 기존 인덱스의 노드(before.next) : prev -> 새로운 노드(newNode)로 설정
삭제 연산
public void deleteFirst() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("리스트가 비어있습니다.");
}
if (this.size == 1) {
this.head = null;
this.tail = null;
}
else {
this.head = head.next;
this.head.prev = null;
}
this.size--;
}
public void deleteLast() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("리스트가 비어있습니다.");
}
if (size == 1) {
this.head = null;
this.tail = null;
}
else {
this.tail = this.tail.prev;
this.tail.next = null;
}
this.size--;
}
public void delete(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났습니다.");
}
if (index == 0) {
this.deleteFirst();
}
else if (index == size - 1) {
this.deleteLast();
}
else {
DoubleNode current = getNodeAtIndex(index);
current.prev.next = current.next;
current.next.prev = current.prev;
this.size--;
}
}
deleteFirst(처음에 삭제하는 경우)
- 노드를 삭제하고 사이즈를 감소시킨다.
- 리스트의 Node가 1개였다면, 삭제 후 head와 tail을 null로 설정한다.
- 그 외의 경우에는 기존 head(삭제할 노드)의 next를 head로 변경한다. 그리고 변경된 head의 prev를 null로 바꾸어준다.
deleteLast(마지막에 삭제하는 경우)
- 노드를 삭제하고 사이즈를 감소시킨다.
- 리스트의 Node가 1개였다면, 삭제 후 head와 tail을 null로 설정한다.
- 그 외의 경우에는 기존 tail(삭제할 노드)의 prev를 tail로 변경한다. 그리고 변경된 tail의 next를 null로 바꾸어준다.
delete(특정 인덱스를 삭제하는 경우)
- 노드를 삭제하고 사이즈를 감소시킨다.
- 삭제할 인덱스의 노드(current)을 탐색한다.
- 삭제할 인덱스의 이전 노드(current.prev) : next -> 삭제할 인덱스의 다음 노드(current.next)로 설정
- 삭제할 인덱스의 다음 노드(current.next) : next -> 삭제할 인덱스의 이전 노드(current.prev)로 설정
이중 연결 리스트 : 전체 코드
class DoubleNode<E> {
E data;
DoubleNode<E> next;
DoubleNode<E> prev;
public DoubleNode(E data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class MyDoubleLinkedList<E> {
private DoubleNode<E> head;
private DoubleNode<E> tail;
private int size;
public MyDoubleLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
public void addFirst(E data) {
DoubleNode node = new DoubleNode(data);
if (isEmpty()) {
this.head = node;
this.tail = node;
}
else {
node.next = head;
this.head.prev = node;
this.head = node;
}
this.size++;
}
public void addLast(E data) {
DoubleNode<E> node = new DoubleNode<>(data);
if (isEmpty()) {
this.head = node;
this.tail = node;
}
else {
this.tail.next = node;
node.prev = tail;
this.tail = node;
}
size++;
}
public void add(int index, E data) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났습니다.");
}
if (index == 0) {
this.addFirst(data);
}
else if (index == size) {
this.addLast(data);
}
else {
DoubleNode<E> newNode = new DoubleNode<>(data);
DoubleNode<E> before = getNodeAtIndex(index - 1);
newNode.next = before.next;
before.next.prev = newNode;
before.next = newNode;
newNode.prev = before;
this.size++;
}
}
public void deleteFirst() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("리스트가 비어있습니다.");
}
if (this.size == 1) {
this.head = null;
this.tail = null;
}
else {
this.head = head.next;
this.head.prev = null;
}
this.size--;
}
public void deleteLast() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("리스트가 비어있습니다.");
}
if (size == 1) {
this.head = null;
this.tail = null;
}
else {
this.tail = this.tail.prev;
this.tail.next = null;
}
this.size--;
}
public void delete(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났습니다.");
}
if (index == 0) {
this.deleteFirst();
}
else if (index == size - 1) {
this.deleteLast();
}
else {
DoubleNode current = getNodeAtIndex(index);
current.prev.next = current.next;
current.next.prev = current.prev;
this.size--;
}
}
public E get(int index) {
DoubleNode<E> node = this.getNodeAtIndex(index);
return node.data;
}
private DoubleNode<E> getNodeAtIndex(int index) {
// 리스트의 절반 이상에 해당하는 인덱스일 경우 뒤에서부터 탐색
if (index > size / 2) {
DoubleNode<E> current = tail;
for (int i = size - 1; i > index; i--) {
current = current.prev;
}
return current;
} else { // 리스트의 절반 이하에 해당하는 인덱스일 경우 앞에서부터 탐색
DoubleNode<E> current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current;
}
}
public boolean isEmpty() {
return size == 0;
}
public int size(){
return size;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
DoubleNode<E> current = head;
while (current != null) {
if (current != head) {
sb.append("-");
}
sb.append(current.data);
current = current.next;
}
return sb.toString();
}
}
public static void main(String[] args) {
MyDoubleLinkedList list = new MyDoubleLinkedList();
list.add(0, 6);
list.add(1, 7);
System.out.println(list); // 6-7
list.addFirst(4);
list.addFirst(3);
list.addFirst(2);
System.out.println(list); // 2-3-4-6-7
list.addLast(8);
list.addLast(9);
list.add(0, 1);
list.add(4, 5);
System.out.println(list); // 1-2-3-4-5-6-7-8-9
list.deleteFirst();
list.deleteLast();
System.out.println(list); // 2-3-4-5-6-7-8
list.delete(1);
System.out.println(list); // 2-4-5-6-7-8
System.out.println(list.get(1)); // 4
}환형 연결 리스트 (Circular Linked List)
일반적인 연결 리스트의 변형으로 마지막 노드가 첫 번째 노드를 가리키는 구조를 가진다. 즉, 연결 리스트의 마지막 노드의 다음 노드는 첫 번째 노드를 가리킨다. 따라서 원형의 구조를 가진다.
순회를 종료하는 조건을 추가로 검사할 필요가 없어 리스트의 순회가 용이하다. 따라서 라운드 로빈과 같은 순환적인 데이터 구조를 모델링하는 데 자주 사용된다. 그렇지만 사이클 무한 루프를 항상 조심해야 한다.
노드와 리스트의 기본 구성
class CircularNode <E> {
E data;
CircularNode<E> next;
public CircularNode(E data){
this.data = data;
this.next = null;
}
}
class MyCircularLinkedList<E>{
protected CircularNode<E> head;
protected CircularNode<E> tail;
private int size; // 연결 리스트의 사이즈
public MyCircularLinkedList(){
this.head = null;
this.tail = null;
size = 0;
}
public boolean isEmpty(){
return size == 0;
}
public int size(){
return size;
}
@Override
public String toString() {
CircularNode current = head;
StringBuilder sb = new StringBuilder();
while (true) {
if(current != head) {
sb.append("->");
}
sb.append(current.data);
if(current == tail){
break;
}
current = current.next;
}
return sb.toString();
}
}
기본적으로 단순 연결 리스트와 유사하다. 다만 리스트에서 마지막 노드를 가리키는 tail을 추가하여, tail에 해당하는 노드의 next는 null이 아니라 맨 처음의 노드를 참조하도록 설계할 것이다.
toString() 함수에서는 환형 순환이므로 기존 순회 방식으로 하게 되면 무한루프를 돌게 된다. 따라서 탈출 조건을 설정해 주어야 한다.
리스트의 처음과 끝에 삽입 / 삭제 시
단순 연결 리스트의 방식에서 다른 점은, 첫 노드와 마지막 노드를 다루는 부분의 변경을 주목해야 한다.
마지막 노드(tail)의 next는 첫 노드(head)를 가리키도록 설정해야 한다.
public void addFirst(E data){
CircularNode<E> node = new CircularNode<>(data);
if (isEmpty()) {
head = node;
tail = node;
tail.next = head; // 환형 연결 리스트이므로 tail의 다음은 head
}
else {
node.next = head;
head = node;
tail.next = head; // head가 새로 추가된 노드를 가리키도록 업데이트
}
size++;
}
public void addLast(E data){
CircularNode node = new CircularNode(data);
if (isEmpty()) {
head = node;
tail = node;
tail.next = head; // 환형 연결 리스트이므로 tail의 다음은 head
}
else {
tail.next = node;
tail = node;
tail.next = head; // tail이 새로 추가된 노드를 가리키도록 업데이트
}
size++;
}
public void deleteFirst(){
if(this.isEmpty()){
throw new IndexOutOfBoundsException("리스트가 비어있습니다.");
}
this.head = this.head.next; // 기존 단순 연결 리스트와 동일하다. tail의 next는 자동으로 새로운 head를 가리킴
this.size--;
}
public void deleteLast(){
if(this.isEmpty()){
throw new IndexOutOfBoundsException("리스트가 비어있습니다.");
}
if(size == 1){
this.head = null;
}
else{
CircularNode before = this.getIndexOfNode(this.size - 2);
before.next = tail; // 새로 변경된 tail의 next를 head로 연결시켜준다.
}
this.size--;
}
전체 코드
class CircularNode <E> {
E data;
CircularNode<E> next;
public CircularNode(E data){
this.data = data;
this.next = null;
}
}
class MyCircularLinkedList<E>{
protected CircularNode<E> head;
protected CircularNode<E> tail;
private int size; // 연결 리스트의 사이즈
public MyCircularLinkedList(){
this.head = null;
this.tail = null;
size = 0;
}
public void addFirst(E data){
CircularNode<E> node = new CircularNode<>(data);
if (isEmpty()) {
head = node;
tail = node;
tail.next = head; // 환형 연결 리스트이므로 tail의 다음은 head
}
else {
node.next = head;
head = node;
tail.next = head; // head가 새로 추가된 노드를 가리키도록 업데이트
}
size++;
}
public void addLast(E data){
CircularNode node = new CircularNode(data);
if (isEmpty()) {
head = node;
tail = node;
tail.next = head; // 환형 연결 리스트이므로 tail의 다음은 head
}
else {
tail.next = node;
tail = node;
tail.next = head; // tail이 새로 추가된 노드를 가리키도록 업데이트
}
size++;
}
// 특정 인덱스에 요소 추가
public void add(int index, E data) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났습니다.");
}
if (index == 0) {
this.addFirst(data);
}
else if (index == size){
this.addLast(data);
}
else{
CircularNode newNode = new CircularNode(data);
CircularNode before = this.getIndexOfNode(index - 1);
//인덱스 이전의 노드 -> 새로운 노드 -> 인덱스 이전의 노드의 다음 노드
newNode.next = before.next;
before.next = newNode;
this.size++;
}
}
public void deleteFirst(){
if(this.isEmpty()){
throw new IndexOutOfBoundsException("리스트가 비어있습니다.");
}
this.head = this.head.next;
this.size--;
}
public void deleteLast(){
if(this.isEmpty()){
throw new IndexOutOfBoundsException("리스트가 비어있습니다.");
}
if(size == 1){
this.head = null;
}
else{
CircularNode before = this.getIndexOfNode(this.size - 2);
before.next = tail;
}
this.size--;
}
// 특정 인덱스에 요소 삭제
public void delete(int index) {
if(index < 0 || index > size - 1){
throw new IndexOutOfBoundsException("인덱스 범위를 벗어났습니다");
}
if (index == 0) {
this.deleteFirst();
}
else if (index == size - 1) {
this.deleteLast();
}
else{
CircularNode before = this.getIndexOfNode(index - 1);
before.next = before.next.next;
this.size--;
}
}
public E get(int index) {
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났습니다.");
}
CircularNode<E> node = this.getIndexOfNode(index);
return node.data;
}
public boolean isEmpty(){
return size == 0;
}
public int size(){
return size;
}
private CircularNode getIndexOfNode(int index){
CircularNode current = head;
for(int i = 0; i < index; i++){
current = current.next;
}
return current;
}
@Override
public String toString() {
CircularNode current = head;
StringBuilder sb = new StringBuilder();
while (true) {
if(current != head) {
sb.append("->");
}
sb.append(current.data);
if(current == tail){
break;
}
current = current.next;
}
return sb.toString();
}
}public static void main(String[] args) {
MyCircularLinkedList list = new MyCircularLinkedList<Integer>();
list.add(0, 6);
list.add(1, 7);
System.out.println(list); // 6->7
list.addFirst(4);
list.addFirst(3);
list.addFirst(2);
System.out.println(list); // 2->3->4->6->7
list.addLast(8);
list.addLast(9);
list.add(0, 1);
list.add(4, 5);
System.out.println(list); // 1->2->3->4->5->6->7->8->9
list.deleteFirst();
list.deleteLast();
System.out.println(list); // 2->3->4->5->6->7->8
list.delete(1);
System.out.println(list); // 2->4->5->6->7->8
System.out.println(list.get(1)); // 4
}
Collection : LinkedList 사용
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("Banana");
linkedList.add("Orange");
linkedList.add("Kiwi");
linkedList.add("Mango");
linkedList.addFirst("Apple");
linkedList.addLast("Grapes");
//LinkedList: [Apple, Banana, Orange, Kiwi, Mango, Grapes]
System.out.println("LinkedList: " + linkedList);
linkedList.remove("Banana");
linkedList.remove(3);
//LinkedList: [Apple, Orange, Kiwi, Grapes]
System.out.println("LinkedList: " + linkedList);
linkedList.removeFirst();
linkedList.removeLast();
//LinkedList: [Orange, Kiwi]
System.out.println("LinkedList: " + linkedList);
String s = linkedList.get(1); // Kiwi
s = linkedList.getFirst(); // Orange
s = linkedList.getLast(); // Kiwi
Java에서 제공하는 Collection의 LinkedList는 이중 연결 리스트(Doubly Linked List)를 기반으로 한 리스트이다.
주요 메서드로는 add(), remove(), addFirst(), addLast(), removeFirst(), removeLast(), get(), getFirst(), getLast()등이 있다.
시간 복잡도
삽입
- 특정 위치에 삽입: O(n) : 순차적으로 탐색해야 하므로 최악의 경우에는 리스트의 길이만큼 순회
- 리스트의 시작이나 끝인 경우
- 단순 연결 리스트의 시작, 이중 연결 리스트 시작과 끝 O(1) : head와 tail을 알고 있으므로
- 단순 연결 리스트의 끝 O(n) : tail을 모르므로
삭제
- 특정 위치에 삭제: O(n) : 순차적으로 탐색해야 하므로 최악의 경우에는 리스트의 길이만큼 순회
- 리스트의 시작이나 끝인 경우
- 단순 연결 리스트의 시작, 이중 연결 리스트 시작과 끝 O(1) : head와 tail을 알고 있으므로
- 단순 연결 리스트의 끝 O(n) : tail을 모르므로
탐색 : O(n) : 순차적으로 탐색해야 하므로 최악의 경우에는 리스트의 길이만큼 순회
반응형
'PS > 자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조/JAVA] 트리 (2) : 이진 탐색 트리(Binary Search Tree, BST) (0) | 2024.03.21 |
|---|---|
| [자료구조/JAVA] 트리 (1) : 이진 트리(Binary Tree) : 순회 및 연산 (0) | 2024.03.19 |
| [자료구조/JAVA] 동적 배열(Dynamic Array) 구현 (1) | 2024.03.12 |
| [자료구조/JAVA] 스택과 큐(Stack, Queue) (0) | 2024.03.11 |
| [알고리즘/JAVA] 재귀와 반복 : 등차수열, 피보나치, 팩토리얼, 하노이탑 (0) | 2024.03.11 |
