链表分为单链表,双向链表和循环链表,是一种链式存储结构,由一个个结点链式构成,结点包含数据域和指针域,其中单链表是只有一个指向后驱结点的指针,双向链表除头结点和尾结点外,每个结点都有一个前驱指针和一个后继指针,循环链表的尾结点的指针指向头结点.
相比数组而言,链表的插入和删除比较快,查询慢.
本文主要以单链表为例,介绍下链表的常用算法操作.
单链表的结构:
在Java语言中,链表的每个结点用Node类来表示:
package com.linkedlist;
public class Node {
private int data;// 结点数据
private Node next;// 下一个结点
public Node(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
定义一个链表操作类,里面包含常用的操作:
package com.linkedlist;
import java.util.Hashtable;
public class LinkedListOperator {
private Node head = null;// 头结点
// 在链表的末尾增加一个结点
private void addNode(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node temp = head;
while (temp.getNext() != null) {
temp = temp.getNext();
}
temp.setNext(newNode);
}
// 打印链表结点
private void printLink() {
Node curNode = head;
while (curNode != null) {
System.out.println(curNode.getData());
curNode = curNode.getNext();
}
System.out.println("===========");
}
// 求链表长度
private int getLength() {
int len = 0;
Node curNode = head;
while (curNode != null) {
len++;
curNode = curNode.getNext();
}
return len;
}
// 删除某一个结点
private boolean delNode(int index) {
if (index < 1) {
return false;
}
if (index == 1) {
head = head.getNext();
return true;
}
Node preNode = head;
Node curNode = head.getNext();
int n = 1;
while (curNode.getNext() != null) {
if (n == index) {
preNode.setData(curNode.getData());
preNode.setNext(curNode.getNext());
return true;
}
preNode = preNode.getNext();
curNode = curNode.getNext();
n++;
}
if (curNode.getNext() == null) {
preNode.setNext(null);
}
return false;
}
// 链表排序:选择排序法,从小到大
private void sortList() {
Node curNode = head;
while (curNode != null) {
Node nextNode = curNode.getNext();
while (nextNode != null) {
if (curNode.getData() > nextNode.getData()) {
int temp = curNode.getData();
curNode.setData(nextNode.getData());
nextNode.setData(temp);
}
nextNode = nextNode.getNext();
}
curNode = curNode.getNext();
}
}