动态链表与静态链表
1. 静态链表
静态链表概述
从他的意义上讲，静态链表像是对没有指针的语言缺陷而产生这么一个补救方法。每个包含了数据域与指针域。相对于C中的指针，这里的指针指的是数组的下标（也称静态指针故将此链表称为静态链表）。
从结构上来说，静态链表分为两个部分，一部分是已存有数据的线性表，另一部分是空闲节点组成的链表，添加新元素不再是申请空间，而是从空闲链表中申请。当下一个指针是-1时代表链表已满。
静态链表优缺点
他综合了顺序表与链表的优点与缺点。
- 空间分配上，静态链表与顺序表一致，预先分配较大空间，但不需要再频繁的开辟回收资源，整体上占用的空间是连续的，不够灵活。
- 数据操作上，又结合了链表的的优势，插入删除效率较高。查询没有顺序表直接。
个人觉得用途不大。
静态链表的实现
研读了一些代码后，最终copy了一份代码，源自：https://blog.csdn.net/u013293125/article/details/52947005
/**
* 因为静态链表实质上是一维数组的存储方式，所以它在物理位置上的存储
* 是顺序的，但它是用游标来指向下一个数据的，所以根据它的下标来获取数据
* 和按照游标的指向来获取数据是不同的，这里设置该链表的头结点为空
* @author Administrator
*
*/
public class StaticLinkList {
private Element[] linkList = null;
private int DEFAULT_SIZE = 4;//默认存储大小
private int currentFree = 0;//指向当前空闲位置
private int size = 1;
class Element{
int data;
int cur;
}
/**
* 静态链表的长度
* @return
*/
public int length(){
return size-1;
}
/**
* 静态链表的初始化
*/
public StaticLinkList(){
linkList = new Element[DEFAULT_SIZE];
for (int i = 0; i < linkList.length; i++) {
linkList[i] = new Element();
linkList[i].data = -1;
linkList[i].cur = i+1;
}
//当前空闲节点从1开始，因为第0个节点设置成了头结点，设置为空，不
//存储数据
currentFree = 1;
}
/**
* 给链表添加数据，每当链表满了就给链表添加额外的空间
* @param data
*/
public void add(int data){
if(size>=linkList.length){
addLinkSpace();
}//链表已满，给链表添加空间
linkList[currentFree].data = data;
currentFree = linkList[currentFree].cur;
size++;
}
/**
* 得到索引指定的数据
* @param index
* @return
*/
public int get(int index){
if(index>size-1&&index<0)
throw new IndexOutOfBoundsException("数组越界，索引不合法");
else{
//这里index+1也是因为多了一个空的头节点
return linkList[index+1].data;//仅仅是索引，并不一定是在链表中的位置
}
}
/**
* 删除指定位置的节点
* @param index
*/
public void delete(int index){
index = index+1;
if(index<1||index>=size){
System.out.println("超出链表长度");
}else if(index == size-1){//删除最后一个数据
size--;
linkList = (Element[]) getTrueIndex(linkList,size);
}else{
int i = 0;
while(index!=linkList[i].cur){//i位置是要删除的数据的前一个索引值
i++;
}
int j = 0;
while(currentFree!=linkList[j].cur){//j是标记当前空闲链表头的前一项，为了将删除的节点加入到空闲链表中
j++;
}
linkList[i].cur = linkList[index].cur;
linkList[j].cur = index;
linkList[index].cur = currentFree;
currentFree = index;
size--;
linkList = (Element[]) getTrueIndex(linkList,size);
}
}
/**
* 增加链表空间
*/
public void addLinkSpace(){
DEFAULT_SIZE+=8;
Element[] link = linkList;
linkList = new Element[DEFAULT_SIZE];
System.arraycopy(link, 0, linkList, 0, link.length);
for (int i = link.length; i < DEFAULT_SIZE; i++) {
linkList[i] = new Element();
linkList[i].data = -1;
linkList[i].cur = i+1;
}
currentFree = link.length;
}
/**
* 根据指定的位置插入数据
* @param index
* @param data
*/
public void insert(int index,int data){
//这里加1的原因是因为链表的第0位为空节点，这里设置的头节点为空
index = index + 1;
if(size<linkList.length){
if(index>size&&index<0)
System.out.println("数组越界，超出数组长度");
else if(index == size){
linkList[currentFree].data = data;
currentFree = linkList[currentFree].cur;
size++;
}else{
/******未按逻辑顺序排序而插入数据的写法，因为未排序，则当前索引的上个节点的索引不一定是当前索引减1****/
int i = 0;
while(index!=linkList[i].cur){
i++;
}
int j = 0;
while(currentFree!=linkList[j].cur){
j++;
}
linkList[i].cur = currentFree;
linkList[j].cur = linkList[currentFree].cur;
linkList[currentFree].data = data;
linkList[currentFree].cur = index;
currentFree = linkList[j].cur;
size++;
//每次插入后将链表按逻辑顺序重新排序，是为了方便输出查看。
linkList = (Element[]) getTrueIndex(linkList,size);
}
}else{
addLinkSpace();
insert(index, data);
}
}
/**
* 按照逻辑顺序重新排列
* @param link
* @return
*/
public Object getTrueIndex(Element[] link,int size){
Element[] linkList1 = new Element[linkList.length];
int k =0;
for (int i = 0; i < linkList.length; i++) {
linkList1[i] = new Element();
linkList1[i].data = link[k].data;
k = link[k].cur;
linkList1[i].cur = i+1;
}
//插入时，currentFree肯定是最后一个了，但删除后，currentFree就不一定是最后一位了
currentFree = size;
return linkList1;
}
}
2. 动态链表
即上节说的链表。由于c具有指针，一般书上都用c实现。他不受初始分配空间限制，占用空间比较灵活，需要一个结点，就申请一个节点。
再copy一份java代码，源自：https://www.cnblogs.com/Y-oung/p/8886142.html
import java.util.Stack;
public class LinkedListOnePoint {
private Node head; //头结点
private int size; //链表长度，即链表中结点数量
public LinkedListOnePoint(){
head = null;
size = 0;
}
//私有内部类，代表链表每个结点
private class Node{
private Object data; //链表结点的值
private Node next; //指向的下一个结点
public Node(Object data){
this.data = data;
}
}
//判断链表是否为空
public boolean isEmpty(){
return size==0?true:false;
}
//返回链表长度
public int size(){
return size;
}
//查看链表头结点，不移除
public Object headNode(){
if(size == 0) return null;
return head.data;
}
//在链表表头插入一个结点（入栈）
public void insertInHead(Object obj){
Node newNode = new Node(obj);
if(size == 0){
head = newNode;
}else{
newNode.next = head;
head = newNode;
}
size++;
}
//删除链表表头结点（出栈）
public Object deleteHeadNode(){
if(size == 0) return null;
Object obj = head.data;
if(head.next == null){
head = null; //只有一个结点
}else{
head = head.next;
}
size--;
return obj;
}
//链表查找：判断链表中是否包含某个元素
public boolean containObject(Object obj){
if(size == 0) return false;
Node n = head;
while(n != null){
if(n.data == obj) return true;
else n = n.next;
}
return false;
}
//删除链表中的指定结点（如果包含多个指定结点，只会删除第一个）
public boolean deleteNode(Object obj){
if(size == 0){
System.out.println("链表为空！");
return false;
}
//先在链表中查询是否包含该结点，找到之后获取该结点和其前一个结点
Node previous = null; //前一个结点
Node current = head; //当前结点
while(current.data != obj){
if(current.next == null){
System.out.println("没有找到该结点！");
return false;
}
previous = current;
current = current.next;
}
if(current == head){
this.deleteHeadNode();
}else{
previous.next = current.next;
size--;
}
return true;
}
//正向打印链表
public void display(){
if(size == 0) System.out.println("链表为空！");
Node n = head;
while(n != null){
System.out.print("<-"+n.data);
n = n.next;
}
System.out.println();
}
//反向打印链表（用栈）
public void printListFromTailToHead(Node node){
if(node == null) System.out.println("链表为空！");
Stack<Integer> sta = new Stack<Integer>();
while(node != null){
sta.push((Integer) node.data); //先将链表压入栈中
node = node.next;
}
while(!sta.empty()){
System.out.print(sta.pop()+"<-"); //出栈
}
System.out.println();
}
//反向打印链表（递归）
public void printListFromTailToHeadDiGui(Node node){
if(node == null){
System.out.println("链表为空！");
}else{
if(node.next != null){
printListFromTailToHeadDiGui(node.next);
}
System.out.print(node.data+"<-");
}
}
public static void main(String[] args) {
LinkedListOnePoint list = new LinkedListOnePoint();
System.out.println(list.isEmpty()); //true
System.out.println(list.size()); //0
list.display(); //链表为空！
list.printListFromTailToHead(list.head); //链表为空！
list.insertInHead(0);
list.insertInHead(1);
list.insertInHead(2);
list.insertInHead(3);
list.display(); //<-3<-2<-1<-0
list.printListFromTailToHead(list.head); //0<-1<-2<-3<-
list.printListFromTailToHeadDiGui(list.head); //0<-1<-2<-3<-
System.out.println(list.isEmpty()); //false
System.out.println(list.size()); //4
System.out.println(list.containObject(1)); //true
}
}
网友评论