对链表的学习(java)
发布日期:2021-05-10 14:37:53 浏览次数:18 分类:精选文章

本文共 7437 字,大约阅读时间需要 24 分钟。

Java LinkedList ���������������������������

��� Java ���������������LinkedList ������������������������������������������������������������������������������������������������������������������������������������������������������������������������������ LinkedList ������������������������������������������������������������������


������ LinkedList ���������������������������

1. ���������

package com.test;
class LinkedNode {
private int data = 0;
public LinkedNode next = null;
public LinkedNode(int data) {
this.data = data;
}
public int getData() {
return this.data;
}
}
  • ������������ (LinkedNode) ���������������������data��������������� next������������������������������
  • ������������������������������������������������ data ��� 0���
  • getData ���������������������������������������

2. LinkedList ���������

public class LinkedList {
private LinkedNode head = null;
// ������������
public void addFirst(int elem) {
LinkedNode node = new LinkedNode(elem);
if (head == null) {
head = node;
return;
}
node.next = head;
head = node;
}
// ������������
public void addLast(int elem) {
LinkedNode node = new LinkedNode(elem);
if (head == null) {
head = node;
} else {
LinkedNode lastNode = lastNode();
lastNode.next = node;
}
}
// ���������������������
public LinkedNode lastNode() {
LinkedNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
return cur;
}
// ��������������������� key ���������
public boolean contains(int key) {
for (LinkedNode cur = head; cur != null; cur = cur.next) {
if (cur.getData() == key) {
return true;
}
}
return false;
}
// ��������������������������������� key
public void remove(int key) {
if (head == null) {
return;
}
if (head.getData() == key) {
head = head.next;
return;
}
LinkedNode prev = previousNode(key);
if (prev != null) {
LinkedNode newNode = prev.next;
prev.next = newNode.next;
}
}
// ��������������� key ������������������
public LinkedNode previousNode(int key) {
if (head == null) {
return null;
}
for (LinkedNode prev = head; prev.next != null; prev = prev.next) {
if (prev.next.getData() == key) {
return prev;
}
}
return null;
}
// ������������������ key ���������
public void removeAllKey(int key) {
if (head == null) {
return;
}
if (head.getData() == key) {
head = head.next;
}
LinkedNode cur = head.next;
LinkedNode prev = head;
while (cur != null) {
if (cur.getData() == key) {
prev.next = cur.next;
cur = prev.next;
} else {
prev = cur;
cur = cur.next;
}
}
}
// ������������������
public boolean addIndex(int index, int elem) {
int length = lengthOfList();
if (index < 0 || index > length) {
return false;
}
if (index == 0 || head == null) {
addFirst(elem);
return true;
}
if (index == length) {
addLast(elem);
return true;
}
LinkedNode prev = toPos(index - 1);
LinkedNode node = new LinkedNode(elem);
node.next = prev.next;
prev.next = node;
return true;
}
// ������������������������
public LinkedNode toPos(int index) {
LinkedNode cur = head;
for (int i = 1; i < index; i++) {
cur = cur.next;
}
return cur;
}
// ������������
public int lengthOfList() {
int length = 0;
for (LinkedNode cur = head; cur != null; cur = cur.next) {
length++;
}
return length;
}
// ������������
public void printList() {
System.out.print("[");
for (LinkedNode cur = head; cur != null; cur = cur.next) {
System.out.print(cur.getData());
if (cur.next != null) {
System.out.print(", ");
}
}
System.out.println("]");
}
// ������������
public void clear() {
head = null;
}
}
  • addFirst ������������������������������������������������������������������������������������
  • addLast ������������������������������������������������������������������������
  • lastNode ���������������������������������������������������������������������������������������
  • contains ���������������������������������������������������������������������������
  • remove ������������������������������������������������������������������������������������������
  • previousNode ���������������������������������������������������������������������������������������
  • removeAllKey ���������������������������������������������������������������
  • addIndex ���������������������������������������������������������������������
  • toPos ������������������������������������������������������������������������������
  • lengthOfList ���������������������������������������������������������������������������������
  • printList ���������������������������������������������������������������
  • clear ������������������������ head ������������ null���

������������������

public class Test {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.addFirst(1);
list.printList(); // ������: [1]
list.addLast(2);
list.printList(); // ������: [1, 2]
list.addIndex(0, 2); // ���������0���������2
list.addIndex(3, 2); // ���������4���������2
list.printList(); // ������: [2, 1, 2, 2]
// ������������������
boolean isContains = list.contains(3); // ���������false
System.out.println("���������������������:" + isContains);
System.out.println("���������������������:" + list.contains(8));
// ������������
list.remove(2); // ������������2������������������
list.printList(); // ������: [1, 2]
list.removeAllKey(2); // ������������������2���������
list.printList(); // ������: [1]
// ������������
list.clear();
list.printList(); // ������: []
}
}

������������������

  • ���������������������������������������������������������������������������������������������������
  • ��������������������� addIndex ������������������������������������������������������������������������������
  • ���������������
    • ��������������� (list.remove(2)) ������������������������ 2���
    • ��������������� (list.removeAllKey(2)) ��������������������� 2���
  • ������������������������������������������������������������������������������������

������

LinkedList ���������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

上一篇:对双向链表的学习
下一篇:对顺序表的学习

发表评论

最新留言

很好
[***.229.124.182]2025年04月04日 15时35分36秒