链表是一种物理上非连续、非顺序的存储结构，数据元素之间的顺序是通过每个元素的指针关联的。
链表有一系列节点组成，每个节点一般至少会包含两部分的信息:(1)元素数据 (2)指向下一个元素的指针
链表分类: (1)单向链表和双向链表 (2)静态链表(数组实现) 、动态链表(指针)
链表的操作: 创建、插入、删除、输出
链表的特点:
(1)物理空间不连续，空间开销更大
(2)在运行时可以动态添加
(3)查找元素需要顺序查找
动态链表的实现代码如下:
package com.threeTop.www; //节点部分的定义 public class Node { private int data; private Node next; /** * 获得数据 * @return */ public int getData() { return data; } /** * 设置数据 * @param data */ public void setData(int data) { this.data=data; } /*** * 获得下一个节点 */ public Node getNext() { return next; } /** * 移动到下一个节点 */ public void setNext(Node next) { this.next=next; } }package com.threeTop.www; /** * 链表的实现 * @author zc * */ public class Link { private int size=0; private Node first; private Node last; /** * 链表的初始化 */ public Link() { } /** * 链表的后部插入 */ public void addLast(int data) { if(size==0) { //为空初始化前后元素 fillStart(data); }else { Node node=new Node(); node.setData(data); //last=this.get(size-1); //找到尾结点 last.setNext(node); last=node; //把最后插入的元素设置为链表尾的元素 } size++; } /*** * 链表头部插入 * @param data */ public void addFirst(int data) { if(size==0) { //为空初始化前后元素 fillStart(data); }else { Node node=new Node(); node.setData(data); node.setNext(first); //把元素的下一个位置的指针指向头元素 first=node; //把刚插入的元素设置为链表头元素 } size++; } /*** * 在链表的指定位置后面插入 * @param data 需要插入的数据 * @param index 下标从0开始 */ public void add(int data ,int index) { if(size>index) { if(size==0) { //为空初始化前后元素 fillStart(data); size++; } else if(index==0) { addFirst(data); } else if(size==index+1) { addLast(data); } else { //在中间的位置插入元素 Node temp=get(index); Node node=new Node(); node.setData(data); node.setNext(temp.getNext()); temp.setNext(node); size++; } } else { throw new IndexOutOfBoundsException("链表没有那么长!"); } } /*** * 获取指定下标元素 * @param index * @return */ private Node get(int index) { // TODO Auto-generated method stub Node temp=first; for(int i=0;i<index;i++) { temp=temp.getNext(); } return temp; } /*** * 初始化链表 * @param data */ private void fillStart(int data) { // TODO Auto-generated method stub first=new Node(); first.setData(data); last=first; //刚开始位置写反了 } /*** * 删除链表的表头元素 */ public void removeFirst() { if(size==0) { throw new IndexOutOfBoundsException("链表没有元素!"); } else if(size==1) { //只剩下一个元素时，清楚first和last clear(); } else { Node temp=first; first=temp.getNext(); temp=null; //头元素删除 size--; } } /*** * 在元素只有一个时清除first和last元素 */ private void clear() { // TODO Auto-generated method stub first=null; last=null; size=0; } /*** * 删除链表的尾部元素 */ public void removeLast() { if(size==0) { throw new IndexOutOfBoundsException("链表没有元素!"); } else if(size==1) { clear(); } else { Node temp=get(size-2);//获取最后一个元素之前的一个元素 temp.setNext(null); size--; } } /*** * 删除链表的中间元素与 */ public void removeMiddle(int index) { if(size==0) { throw new IndexOutOfBoundsException("链表没有元素!"); } else if(size==1) { clear(); } else { if(index==0) { removeFirst(); } else if(size==index-1) { removeLast(); } else { Node temp=get(index-1); //获得删除元素的前一个元素 Node next=temp.getNext(); temp.setNext(next.getNext()); next=null; size--; } } } /*** * 打印所有元素的数据 */ public void printAll() { Node temp=first; System.out.print(temp.getData()+" "); for(int i =0;i<size-1;i++) { temp=temp.getNext(); System.out.print(temp.getData()+" "); //挨个输出链表中的元素 } } /** * 获得链表的大小 */ public int size() { return size; } /** * 反转链表 */ public void reverse() { Node temp=first; last=temp; Node next=first.getNext(); for(int i=0;i<size-1;i++) { Node nextnext=next.getNext(); //下下个 next.setNext(temp); temp=next; next=nextnext; } last.setNext(null); first=temp; } /*** * main函数 * @param args */ public static void main(String [] args) { Link link=new Link(); link.addFirst(5); link.addFirst(1); link.addFirst(2); link.addFirst(3); link.addLast(3); link.addLast(4); link.add(1, 1); //在下标为1的元素之后插入元素 link.printAll(); //打印所有的元素 link.removeFirst(); System.out.println(); link.printAll(); //打印所有的元素 link.removeLast(); System.out.println(); link.printAll(); //打印所有的元素 link.removeMiddle(3); System.out.println(); link.printAll(); //打印所有的元素 System.out.println(); System.out.println("链表的大小:"+link.size()); link.reverse(); //反转链表 System.out.println(); link.printAll(); //打印所有的元素 } }输出结果:
