链表分为单链表,双向链表和循环链表,是一种链式存储结构,由一个个结点链式构成,结点包含数据域和指针域,其中单链表是只有一个指向后驱结点的指针,双向链表除头结点和尾结点外,每个结点都有一个前驱指针和一个后继指针,循环链表的尾结点的指针指向头结点.

相比数组而言,链表的插入和删除比较快,查询慢.

本文主要以单链表为例,介绍下链表的常用算法操作.

单链表的结构:

在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;
    }