지역 사회 배우다 도구 라이브러리 여가
찾다
한국어
집 > Java > java지도 시간 > 단일 연결 목록 및 이중 연결 목록 데이터 구조의 Java 시뮬레이션 예

단일 연결 목록 및 이중 연결 목록 데이터 구조의 Java 시뮬레이션 예

高洛峰
풀어 주다： 2017-01-24 16:05:44
원래의
1590명이 탐색했습니다.

단일 연결 목록 시뮬레이션

선형 테이블:
선형 테이블(시퀀스 테이블이라고도 함)은 가장 기본적이고 단순하며 가장 일반적으로 사용되는 데이터 구조입니다.
선형 테이블의 데이터 요소 간의 관계는 일대일 관계입니다. 즉, 첫 번째와 마지막 데이터 요소를 제외하고 다른 데이터 요소는 끝에서 끝까지 연결됩니다.
선형 테이블은 단순한 논리적 구조를 가지고 있어 구현과 운영이 쉽습니다.
실제 응용에서는 선형 테이블이 스택, 큐, 문자열과 같은 특수 선형 테이블 형태로 사용됩니다.
선형 구조의 기본 특성은 다음과 같습니다.
1. 세트에는 "첫 번째 요소"가 하나만 있어야 합니다.
2. 세트에는 "마지막 요소"가 하나만 있어야 합니다.
3. 마지막 요소를 제외한 모든 요소에는 고유한 후속 요소(결과)가 있습니다.
4. 첫 번째 요소를 제외한 모든 요소에는 고유한 전구체(전건)가 있습니다.

연결된 목록: 연결된 목록
연결된 목록은 물리적 저장 단위의 비연속적이고 비순차적인 저장 구조입니다. 데이터 요소의 논리적 순서는 포인터의 연결 순서를 통해 구현됩니다. 연결 목록
각 데이터 항목은 "링크"에 포함되어 있습니다.
링크 포인트는 Link라고 불리는 클래스의 객체입니다. 연결된 목록에는 유사한 링크 포인트가 많이 있으며 각 링크에는 다음 링크 포인트를 참조하는 next 필드가 포함되어 있습니다.
연결된 목록 개체 자체는 첫 번째 링크 지점에 대한 참조를 먼저 저장합니다. (첫 번째가 없으면 위치 지정이 불가능합니다.)
연결된 리스트는 배열처럼 데이터 항목에 직접 접근할 수 없지만(첨자를 사용하여), 찾을 데이터 간의 관계, 즉 다음 항목에 접근해야 합니다. 링크 포인트가 참조하는 링크 필요한 데이터에 접근할 때까지 클릭하고 다음 링크
체인의 선두에 삽입하고 삭제하는 시간 복잡도는 O(1)입니다. 포인터만 변경하면 되기 때문입니다. 지정된 결과 포인트를 찾아 삭제하기 위한 참조의 경우 지정된 노드 뒤에 삽입하면 이 작업은 평균적으로 연결된 목록에 있는 노드의 절반을 검색해야 하며 효율성은 O(N)입니다.
단일 연결 리스트:
선형 리스트를 "노드의 순서"로 표현하는 것을 선형 연결 리스트(단일 연결 리스트)라고 합니다.
연쇄 액세스 데이터 구조로, 집합에 저장됩니다. 임의의 주소가 있는 저장 단위입니다. 선형 테이블의 데이터 요소입니다. (이 저장 단위 그룹은 연속적이거나 불연속적일 수 있습니다)
링크 포인트의 구조:

단일 연결 목록 및 이중 연결 목록 데이터 구조의 Java 시뮬레이션 예

노드 값을 저장하는 데이터 필드 데이터 ;포인터 다음 노드의 참조를 저장하는 필드(체인 필드)

연결 리스트는 각 노드의 링크 필드를 통해 선형 리스트의 n개 노드를 논리적 순서에 따라 연결합니다.
각 노드에 대해 하나의 링크 필드만 있는 연결 목록을 단일 연결 목록이라고 합니다. 한 방향에서는 후속 노드에 대한 참조만 있습니다. 

/** 
 * 单链表:头插法 后进先出 
 * 将链表的左边称为链头，右边称为链尾。 
 * 头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。 
 * 头插法最先得到的是尾结点 
 * @author stone 
 */
public class SingleLinkedList<T> { 
    
  private Link<T> first;    //首结点 
  public SingleLinkedList() { 
      
  } 
    
  public boolean isEmpty() { 
    return first == null; 
  } 
    
  public void insertFirst(T data) {// 插入 到 链头 
    Link<T> newLink = new Link<T>(data); 
    newLink.next = first; //新结点的next指向上一结点 
    first = newLink; 
  } 
    
  public Link<T> deleteFirst() {//删除 链头 
    Link<T> temp = first; 
    first = first.next; //变更首结点，为下一结点 
    return temp; 
  } 
    
  public Link<T> find(T t) { 
    Link<T> find = first; 
    while (find != null) { 
      if (!find.data.equals(t)) { 
        find = find.next; 
      } else { 
        break; 
      } 
    } 
    return find; 
  } 
    
  public Link<T> delete(T t) { 
    if (isEmpty()) { 
      return null; 
    } else { 
      if (first.data.equals(t)) { 
        Link<T> temp = first; 
        first = first.next; //变更首结点，为下一结点 
        return temp; 
      } 
    } 
    Link<T> p = first; 
    Link<T> q = first; 
    while (!p.data.equals(t)) { 
      if (p.next == null) {//表示到链尾还没找到 
        return null; 
      } else { 
        q = p; 
        p = p.next; 
      } 
    } 
      
    q.next = p.next; 
    return p; 
  } 
    
  public void displayList() {//遍历 
    System.out.println("List (first-->last):"); 
    Link<T> current = first; 
    while (current != null) { 
      current.displayLink(); 
      current = current.next; 
    } 
  } 
    
  public void displayListReverse() {//反序遍历 
    Link<T> p = first, q = first.next, t; 
    while (q != null) {//指针反向，遍历的数据顺序向后 
      t = q.next; //no3 
      if (p == first) {// 当为原来的头时，头的.next应该置空 
        p.next = null; 
      } 
      q.next = p;// no3 -> no1 pointer reverse 
      p = q; //start is reverse 
      q = t; //no3 start 
    } 
    //上面循环中的if里，把first.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给first 
    first = p;  
    displayList(); 
  } 
    
  class Link<T> {//链结点 
    T data;   //数据域 
    Link<T> next; //后继指针，结点    链域 
    Link(T data) { 
      this.data = data; 
    } 
    void displayLink() { 
      System.out.println("the data is " + data.toString()); 
    } 
  } 
    
  public static void main(String[] args) { 
    SingleLinkedList<Integer> list = new SingleLinkedList<Integer>(); 
    list.insertFirst(33); 
    list.insertFirst(78); 
    list.insertFirst(24); 
    list.insertFirst(22); 
    list.insertFirst(56); 
    list.displayList(); 
      
    list.deleteFirst(); 
    list.displayList(); 
      
    System.out.println("find:" + list.find(56)); 
    System.out.println("find:" + list.find(33)); 
      
    System.out.println("delete find:" + list.delete(99)); 
    System.out.println("delete find:" + list.delete(24)); 
    list.displayList(); 
    System.out.println("----reverse----"); 
    list.displayListReverse(); 
  } 
}
로그인 후 복사

인쇄

List (first-->last):
the data is 56
the data is 22
the data is 24
the data is 78
the data is 33
List (first-->last):
the data is 22
the data is 24
the data is 78
the data is 33
find:null
find:linked_list.SingleLinkedList$Link@4b71bbc9
delete find:null
delete find:linked_list.SingleLinkedList$Link@17dfafd1
List (first-->last):
the data is 22
the data is 78
the data is 33
----reverse----
List (first-->last):
the data is 33
the data is 78
the data is 22
로그인 후 복사

단일 연결 목록: 꼬리 삽입 방식, 후입선출 - 연결 목록의 왼쪽 끝이 고정되면 연결 목록이 오른쪽으로 계속 확장됩니다. 목록을 꼬리 삽입 방법이라고 합니다.

tail 삽입 방식은 연결 리스트 생성 시 헤드 포인터가 고정되어 있으므로 연결 리스트의 오른쪽까지 확장되도록 tail 포인터를 설정해야 합니다.
tail 삽입 방식으로 얻은 첫 번째 사항입니다. 헤드 노드입니다. 

public class SingleLinkedList2<T> {
    
  private Link<T> head;   //首结点
  public SingleLinkedList2() {
      
  }
    
  public boolean isEmpty() {
    return head == null;
  }
    
  public void insertLast(T data) {//在链尾 插入
    Link<T> newLink = new Link<T>(data);
    if (head != null) {
      Link<T> nextP = head.next;
      if (nextP == null) {
        head.next = newLink;
      } else {
        Link<T> rear = null;
        while (nextP != null) {
          rear = nextP;
          nextP = nextP.next;
        }
        rear.next = newLink;
      }
    } else {
      head = newLink;
    }
  }
    
  public Link<T> deleteLast() {//删除 链尾
    Link<T> p = head;
    Link<T> q = head;
    while (p.next != null) {// p的下一个结点不为空，q等于当前的p(即q是上一个，p是下一个) 循环结束时，q等于链尾倒数第二个
      q = p;
      p = p.next;
    }
    //delete
    q.next = null;
    return p;
  }
    
  public Link<T> find(T t) {
    Link<T> find = head;
    while (find != null) {
      if (!find.data.equals(t)) {
        find = find.next;
      } else {
        break;
      }
    }
    return find;
  }
    
  public Link<T> delete(T t) {
    if (isEmpty()) {
      return null;
    } else {
      if (head.data.equals(t)) {
        Link<T> temp = head;
        head = head.next; //变更首结点，为下一结点
        return temp;
      }
    }
    Link<T> p = head;
    Link<T> q = head;
    while (!p.data.equals(t)) {
      if (p.next == null) {//表示到链尾还没找到
        return null;
      } else {
        q = p;
        p = p.next;
      }
    }
      
    q.next = p.next;
    return p;
  }
    
  public void displayList() {//遍历
    System.out.println("List (head-->last):");
    Link<T> current = head;
    while (current != null) {
      current.displayLink();
      current = current.next;
    }
  }
    
  public void displayListReverse() {//反序遍历
    Link<T> p = head, q = head.next, t;
    while (q != null) {//指针反向，遍历的数据顺序向后
      t = q.next; //no3
      if (p == head) {// 当为原来的头时，头的.next应该置空
        p.next = null;
      }
      q.next = p;// no3 -> no1 pointer reverse
      p = q; //start is reverse
      q = t; //no3 start
    }
    //上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head
    head = p; 
    displayList();
  }
    
  class Link<T> {//链结点
    T data;   //数据域
    Link<T> next; //后继指针，结点    链域
    Link(T data) {
      this.data = data;
    }
    void displayLink() {
      System.out.println("the data is " + data.toString());
    }
  }
    
  public static void main(String[] args) {
    SingleLinkedList2<Integer> list = new SingleLinkedList2<Integer>();
    list.insertLast(33);
    list.insertLast(78);
    list.insertLast(24);
    list.insertLast(22);
    list.insertLast(56);
    list.displayList();
      
    list.deleteLast();
    list.displayList();
      
    System.out.println("find:" + list.find(56));
    System.out.println("find:" + list.find(33));
      
    System.out.println("delete find:" + list.delete(99));
    System.out.println("delete find:" + list.delete(78));
    list.displayList();
    System.out.println("----reverse----");
    list.displayListReverse();
  }
}
로그인 후 복사

인쇄

List (head-->last):
the data is 33
the data is 78
the data is 24
the data is 22
the data is 56
List (head-->last):
the data is 33
the data is 78
the data is 24
the data is 22
find:null
find:linked_list.SingleLinkedList2$Link@4b71bbc9
delete find:null
delete find:linked_list.SingleLinkedList2$Link@17dfafd1
List (head-->last):
the data is 33
the data is 24
the data is 22
----reverse----
List (head-->last):
the data is 22
the data is 24
the data is 33
로그인 후 복사

양단 연결 목록 시뮬레이션 및 연결 목록 사용 스택 및 큐 구현

이중 종료 연결 목록:
이중 종료 연결 목록은 기존 연결 목록과 매우 유사하며 마지막 링크 지점에 참조라는 새로운 속성을 추가합니다.
이렇게 하면 체인 끝에 삽입하기가 매우 쉽습니다. 마지막 노드
를 검색하기 위해 반복하는 대신 새 노드 옆에 있는 후면을 변경하면 됩니다. 따라서 insertFirst 및 insertLast
를 사용하여 링크 헤드를 삭제할 때 참조점만 변경하면 됩니다. 링크를 삭제하면 끝에서 두 번째 노드의 다음은 공백으로 남겨두어야 합니다.
이를 가리키는 참조가 없으므로 작업을 읽으려면 여전히 루프가 필요합니다. 

/**
 * 双端链表
 * @author stone
 */
public class TwoEndpointList<T> {
  private Link<T> head;   //首结点
  private Link<T> rear;   //尾部指针
    
  public TwoEndpointList() {
      
  }
    
  public T peekHead() {
    if (head != null) {
      return head.data;
    }
    return null;
  }
    
  public boolean isEmpty() {
    return head == null;
  }
    
  public void insertFirst(T data) {// 插入 到 链头
    Link<T> newLink = new Link<T>(data);
    newLink.next = head; //新结点的next指向上一结点
    head = newLink;
  }
    
  public void insertLast(T data) {//在链尾 插入
    Link<T> newLink = new Link<T>(data);
    if (head == null) {
      rear = null;
    }
    if (rear != null) {
      rear.next = newLink;
    } else {
      head = newLink;
      head.next = rear;
    }
    rear = newLink; //下次插入时，从rear处插入
      
  }
    
  public T deleteHead() {//删除 链头
    if (isEmpty()) return null;
    Link<T> temp = head;
    head = head.next; //变更首结点，为下一结点
    if (head == null) {
    <span style="white-space:pre">  </span>rear = head;
    }
    return temp.data;
  }
    
  public T find(T t) {
    if (isEmpty()) {
      return null;
    }
    Link<T> find = head;
    while (find != null) {
      if (!find.data.equals(t)) {
        find = find.next;
      } else {
        break;
      }
    }
    if (find == null) {
      return null;
    }
    return find.data;
  }
    
  public T delete(T t) {
    if (isEmpty()) {
      return null;
    } else {
      if (head.data.equals(t)) {
        Link<T> temp = head;
        head = head.next; //变更首结点，为下一结点
        return temp.data;
      }
    }
    Link<T> p = head;
    Link<T> q = head;
    while (!p.data.equals(t)) {
      if (p.next == null) {//表示到链尾还没找到
        return null;
      } else {
        q = p;
        p = p.next;
      }
    }
    q.next = p.next;
    return p.data;
  }
    
  public void displayList() {//遍历
    System.out.println("List (head-->last):");
    Link<T> current = head;
    while (current != null) {
      current.displayLink();
      current = current.next;
    }
  }
    
  public void displayListReverse() {//反序遍历
    if (isEmpty()) {
      return;
    }
    Link<T> p = head, q = head.next, t;
    while (q != null) {//指针反向，遍历的数据顺序向后
      t = q.next; //no3
      if (p == head) {// 当为原来的头时，头的.next应该置空
        p.next = null;
      }
      q.next = p;// no3 -> no1 pointer reverse
      p = q; //start is reverse
      q = t; //no3 start
    }
    //上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head
    head = p; 
    displayList();
  }
    
  class Link<T> {//链结点
    T data;   //数据域
    Link<T> next; //后继指针，结点    链域
    Link(T data) {
      this.data = data;
    }
    void displayLink() {
      System.out.println("the data is " + data.toString());
    }
  }
    
  public static void main(String[] args) {
    TwoEndpointList<Integer> list = new TwoEndpointList<Integer>();
    list.insertLast(1);
    list.insertFirst(2);
    list.insertLast(3);
    list.insertFirst(4);
    list.insertLast(5);
    list.displayList();
      
    list.deleteHead();
    list.displayList();
      
    System.out.println("find:" + list.find(6));
    System.out.println("find:" + list.find(3));
  
    System.out.println("delete find:" + list.delete(6));
    System.out.println("delete find:" + list.delete(5));
    list.displayList();
    System.out.println("----reverse----");
    list.displayListReverse();
  }
}
로그인 후 복사

인쇄

List (head-->last):
the data is 4
the data is 2
the data is 1
the data is 3
the data is 5
List (head-->last):
the data is 2
the data is 1
the data is 3
the data is 5
find:null
find:3
delete find:null
delete find:5
List (head-->last):
the data is 2
the data is 1
the data is 3
----reverse----
List (head-->last):
the data is 3
the data is 1
the data is 2
로그인 후 복사

연결된 목록을 사용하여 스택을 구현합니다.

이 클래스는 이중 종료 연결 목록을 사용하여 다음을 구현합니다. 

public class LinkStack<T> {
  private TwoEndpointList<T> datas;
    
  public LinkStack() {
    datas = new TwoEndpointList<T>();
  }
    
  // 入栈
  public void push(T data) {
    datas.insertFirst(data);
  }
    
  // 出栈
  public T pop() {
    return datas.deleteHead();
  }
    
  // 查看栈顶
  public T peek() {
    return datas.peekHead();
  }
    
  //栈是否为空
  public boolean isEmpty() {
    return datas.isEmpty();
  }
    
  public static void main(String[] args) {
    LinkStack<Integer> stack = new LinkStack<Integer>();
    for (int i = 0; i < 5; i++) {
      stack.push(i);
    }
    for (int i = 0; i < 5; i++) {
      Integer peek = stack.peek();
      System.out.println("peek:" + peek);
    }
    for (int i = 0; i < 6; i++) {
      Integer pop = stack.pop();
      System.out.println("pop:" + pop);
    }
      
    System.out.println("----");
    for (int i = 5; i > 0; i--) {
      stack.push(i);
    }
    for (int i = 5; i > 0; i--) {
      Integer peek = stack.peek();
      System.out.println("peek:" + peek);
    }
    for (int i = 5; i > 0; i--) {
      Integer pop = stack.pop();
      System.out.println("pop:" + pop);
    }
  }
}
로그인 후 복사

인쇄

peek:4
peek:4
peek:4
peek:4
peek:4
pop:4
pop:3
pop:2
pop:1
pop:0
pop:null
----
peek:1
peek:1
peek:1
peek:1
peek:1
pop:1
pop:2
pop:3
pop:4
pop:5
로그인 후 복사

연결 목록 구현 대기열 이중 종료 연결 목록을 사용한 구현: 

public class LinkQueue<T> {
  private TwoEndpointList<T> list;
    
  public LinkQueue() {
    list = new TwoEndpointList<T>();
  }
  //插入队尾
  public void insert(T data) {
    list.insertLast(data);
  }
  //移除队头
  public T remove() {
    return list.deleteHead();
  }
  //查看队头
  public T peek() {
    return list.peekHead();
  }
    
  public boolean isEmpty() {
    return list.isEmpty();
  }
    
  public static void main(String[] args) {
    LinkQueue<Integer> queue = new LinkQueue<Integer>();
    for (int i = 1; i < 5; i++) {
      queue.insert(i);
    }
    for (int i = 1; i < 5; i++) {
      Integer peek = queue.peek();
      System.out.println("peek:" + peek);
    }
    for (int i = 1; i < 5; i++) {
      Integer remove = queue.remove();
      System.out.println("remove:" + remove);
    }
      
    System.out.println("----");
      
    for (int i = 5; i > 0; i--) {
      queue.insert(i);
    }
    for (int i = 5; i > 0; i--) {
      Integer peek = queue.peek();
      System.out.println("peek2:" + peek);
    }
    for (int i = 5; i > 0; i--) {
      Integer remove = queue.remove();
      System.out.println("remove:" + remove);
    }
  }
}
로그인 후 복사

인쇄

peek:1
peek:1
peek:1
peek:1
remove:1
remove:2
remove:3
remove:4
----
peek2:5
peek2:5
peek2:5
peek2:5
peek2:5
remove:5
remove:4
remove:3
remove:2
remove:1
로그인 후 복사

단일 연결 목록 및 이중 연결 목록 데이터 구조의 Java 시뮬레이션에 대한 더 많은 예를 보려면 PHP 중국어 웹사이트에서 관련 기사를 주목하세요!


관련 라벨：
Java 链表
원천：php.cn
이전 기사：순서 연결 목록 데이터 구조의 Java 시뮬레이션 예 다음 기사：Java에서는 단일 연결 목록과 이중 연결 목록을 구현합니다.
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
최신 이슈
특정 클릭 이벤트를 수신하고 다른 클릭 이벤트는 억제하는 방법은 무엇입니까? 내 웹 애플리케이션에는 각 행이 특정 URL(<table><trdata-url="https://www.google.com">...
에서 2024-04-04 16:55:27
0
1
317
내 CSS 스타일시트가 더 이상 작동하지 않거나 HTML 파일에 대한 링크가 작동하지 않습니다. 이유가 무엇일까요? 답변을 찾기 위해 많은 포럼을 검색했고 약 50개의 Google 링크를 살펴봤지만 작동하는 항목을 찾지 못했습니다. 내 CSS가 내 HTML에 표시되지 않습니다....
에서 2024-04-03 09:49:45
0
1
402
CSS: 목록 항목 사이의 간격 수정 목록의 CSS를 편집하려고 시도했지만 행으로 올바르게 이동하고 목록 요소 사이의 높이를 조정하는 방법을 찾지 못했습니다. 웹사이트 링크: https://denki...
에서 2024-04-02 15:46:38
0
1
342
요소 내에서 여러 항목 정렬: 단계별 가이드 하나의 요소 안에 다른 항목을 정렬하고 싶습니다! Element에 flexbox를 제공하고 그 안의 항목을 직접 조정해 보았습니다! 하지만 제대로 반응하지 않습니...
에서 2024-04-01 23:21:40
0
2
366
토스트 UI 홈페이지와 유사한 탐색 모음 만들기 영감의 원천 저는 다음과 같은 네비게이션 바를 만들고 싶었습니다. Toastui 홈 페이지 제가 한 일은 이것을 달성하기 위해 가능한 한 많이 복사하려고 했습니다...
에서 2024-04-01 18:34:38
0
1
240
관련 주제
더>
인기 추천
인기 튜토리얼
더>
관련 튜토리얼
인기 추천
최신 강좌
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿