链结点
在链表中，每个数据项都被包含在‘点“中，一个点是某个类的对象，这个类可认叫做
LINK。因为一个链表中有许多类似的链结点，所以有必要用一个不同于链表的类来表达
链结点。每个 LINK 对象中都包含一个对下一个点引用的字段（通常叫做 next）但是
本身的对象中有一个字段指向对第一个链结点的引用
单链表是一种顺序存取的结构，为找第 i个数据元素，必须先找到第 i-1个数
据元素。因此，查找第i个数据元素的基本操作为：移动指针，比较 j 和 i
1、链接存储方法
链接方式存储的线性表简称为链表（LinkedList ）。
链表的具体存储表示为：
① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，
也可以是不连续的）
② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻
辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信
息（称为指针（pointer ）或链(link) ）
注意：
链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示
各种非线性的数据结构。
2 、链表的结点结构
┌──┬──┐
│data │next │
└──┴──┘
data 域--存放结点值的数据域
next 域--存放结点的直接后继的地址（位置）的指针域（链域）
注意：
①链表通过每个结点的链域将线性表的 n 个结点按其逻辑顺序链接在一起的。
②每个结点只有一个链域的链表称为单链表（Single Linked List ）。
3 、头指针 head 和终端结点指针域的表示
单链表中每个结点的存储地址是存放在其前趋结点 next 域中，而开始结点无前
趋，故应设头指针 head 指向开始结点。
注意：
链表由头指针唯一确定，单链表可以用头指针的名字来命名。
【例】头指针名是 head 的链表可称为表 head 。
终端结点无后继，故终端结点的指针域为空，即 NULL 。
[java] view plain copy print ? public class LinkList { public class Node{ //定义节点 private T data; private Node next; public Node(){ } public Node(T data,Node next){ this.data=data; this.next=next; } } private Node header;//头节点 private Node tail;//尾节点 private int size;//链表大小 //构造函数初始化数据 public LinkList(){ header=null; tail=null; } public LinkList(T element){ header=new Node(element,null); tail=header; size++; } //链表长度 public int length(){ return size; } //返回指定位置index的节点 public T get(int index){ return getNodeByIndex(index).data; } private Node getNodeByIndex(int index) { if(index<</span>0||index>size-1){ throw new IndexOutOfBoundsException("线性表索引越界"); } Node current=header; for(int i=0;inull;i++,current=current.next){ if(i==index){ return current; } } return null; } //返回element在链表的位置，-1表示不存在 public int locate(T element){ Node current=header; for(int i=0;inull;i++,current=current.next){ if(current.data==element){ return i; } } return -1; } //在index位置插入节点element public void insert(T element,int index){ if(index<</span>0||index>size){ throw new IndexOutOfBoundsException("线性表索引越界"); } if(header==null){ add(element); }else{ if(index==0){ addAtHeader(element); }else{ Node prev=getNodeByIndex(index-1); prev.next=new Node(element,prev.next); size++; } } } //采用尾插法为链表添加新节点 private void add(T element) { // TODO Auto-generated method stub if(header==null){ header=new Node(element,null); tail=header; }else{ Node newNode=new Node(element,null); tail.next=newNode; tail=newNode; } size++; } //采用头插法为链表添加新节点 private void addAtHeader(T element){ header=new Node(element,header); if(tail==null){ tail=header; } size++; } //删除index位置的节点 public T delete(int index){ if(index<</span>0||index>size-1){ throw new IndexOutOfBoundsException("线性表索引越界"); } Node del=null; if(index==0){ del=header; header=header.next; }else{ Node prev=getNodeByIndex(index-1); del=prev.next; prev.next=del.next; del.next=null; } size--; return del.data; } //从链表后面删除一个节点 public T remove(){ return delete(size-1); } //是否为空 public boolean empty(){ return size==0; } //清空链表 public void clear(){ header=null; tail=null; size=0; } public String toString(){ if(empty()){ return "[]"; }else{ StringBuilder sb=new StringBuilder("["); for(Node current=header;current!=null;current=current.next){ sb.append(current.data.toString()+", "); } int len=sb.length(); return sb.delete(len-2, len).append("]").toString(); } } public static void main(String[] args) { LinkList list=new LinkList(); list.insert("aaa", 0); list.add("bbb"); list.add("ccc"); System.out.println(list.toString()); list.insert("ddd", 1); System.out.println(list.toString()); list.delete(2); System.out.println(list.toString()); System.out.println("ccc在链表中的位置："+list.locate("ccc")); System.out.println("链表中索引2处的元素："+list.get(2)); } }
