Java实现线性表的链式存储

Java实现线性表的链式存储

本文实例为大家分享了java实现线性表的链式存储，供大家参考，具体内容如下

链表：一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

package algorithm.datastructure.linklist;

import java.util.NoSuchElementException;

/*

* 链表

* 物理存储上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现

*

* */

public class LinkedList {

private Node head;//头节点

private int size;//链表长度

static private class Node{

private int data;

private Node next;

public Node(){

}

private Node(int data,Node next){

this.data=data;

this.next=next;

}

}

//初始化空链表

public LinkedList(){

//head=null;

}

//添加元素

public Boolean add(int element){

linkLast(element);

return true;

}

//在某个位置之前添加元素

public Boolean add(int index,Integer element){

checkPositionIndex(index);

if (index==size){

linkLast(element);

} else {

linkBefore(element,node(index));

}

return true;

}

//根据下标获取元素

public int get(int index){

checkElementIndex(index);

returqyfnLLQn node(indexqyfnLLQ).data;

}

//获取第一个元素

public Integer getFirst(){

Node f=head;

if (f==null){

throw new NoSuchElementException();

} else {

return f.data;

}

}

//获取最后一个元素

public Integer getLast(){

if (size==0){

throw new NoSuchElementException();

}

int index=size-1;

return node(index).data;

}

//删除第一个元素

public Integer removeFirst(){

Node f=head;

if (f==null){

throw new NoSuchElementException();

} else {

return unlink(head);

}

}

//删除最后一个元素

public Integer removeLast(){

if (size==0){

throw new NoSuchElementException();

}

int index=size-1;

return unlink(node(index));

}

//根据索引删除元素

public Integer remove(int index){

checkElementIndex(index);

return unlink(node(index));

}

//销毁链表

public void destroyList(){

clearList();

}

//将链表置为空表

public void clearList() {

for (Node p=head;p!=null;){

Node next=p.next;//记录下一个结点

p=null;//删除当前结点

p=next;//指向下一个结点

}

size=0;

head=null;

}

//遍历链表

public void traverseList(){

for (Node p=head;p!=null;){

System.out.println(p.data);

p=p.next;

}

}

//返回链表元素个数

public int size(){

return size;

}

//尾部添加结点

private void linkLast(int element){

Node cur =null,p;

if (size==0){//没有结点时

head=new Node(element,null);

size++;

return;

}

for (p=head;p!=null;){//有结点时候

cur=p;

p=cur.next;

}

cur.next= new Node(element,null);//尾部添加元素

size++;

}

//在某结点之前插入结点

private void linkBefore(int element,Node node){

if (node==null){

linkLast(element);

} else {

Node p=head,q=p.next;

if (node.data==p.data){//node为结点时候

head= new Node(element, p);//在头部插入元素

size++;

} else {

while (p!=null){

if (q.data==node.data) {

p.next= new Node(element,q);//在q之前(p之后)插入一个元素

size++;

break;

}

p=p.next;

q=p.next;

}

}

}

}

//删除结点

private Integer unlink(Node node){

Integer deleteNodeData=null;

Node p=null;

deleteNodeData=node.data;

if (node.data==head.data){//该节点为头结点

p=head;

head=p.next;

p=null;

size--;

} else {

Node q=head;

for (p=q.next;p!=null;){//使用两个指针,p,q

if (p.data==node.data){

break;

}

q=q.next;//p始终为q的next结点

p=q.next;

}

q.next=p.next;

p=null;//删除p

size--;

}

return deleteNodeData;

}

//数组下标是否越界

private Boolean isElementIndex(int index){

return index>=0&&index

}

//插入位置是否越界

public Boolean isPositionIndex(int index){

return index>=0&&index<=size;

}

//检验下标是否越界，抛出异常

private void checkElementIndex(int index){

if(!isElementIndex(index)){

try {

throw new IndexOutOfBoundsException("下标越界");

} catch (Exception e) {

e.printStackTrace();

}

}

}

//检验插入下标是否越界，抛出异常

private void checkPositionIndex(int index){

if(!isPositionIndex(index)){

try {

throw new IndexOutOfBoundsException("下标越界");

} catch (Exception e) {

e.printStackTrace();

}

}

}

//返回指定位置的元素

private Node node(int index){

int nowIndex = 0;

if(size>0){

for (Node p=head;p!=null;){

if (nowIndex==index){

return p;

}

p=p.next;

nowIndex++;

}

}

return null;

}

public static void main(String[] args) {

java.util.LinkedList linkedList0=new java.util.LinkedList();

linkedList0.add(6);

linkedList0.remove(0);

linkedList0.size();

linkedList0.peek();

//linkedList0.getFirst();

linkedList0.clear();

//测试

LinkedList linkedList=new LinkedList();

linkedList.add(2);

linkedList.add(6);

linkedList.add(0);

linkedList.add(3);

linkedList.add(8);

linkedList.add(10);

System.out.println(linkedList.get(0));

System.out.println(linkedList.getFirst());

System.out.println(linkedList.getLast());

System.out.println(linkedList.get(5));

System.out.println(linkedList.remove(5));

System.out.println(linkedList.remove(4));

linkedList.remove(2);

linkedList.remove(0);

linkedList.remove(0);

linkedList.remove(0);

linkedList.add(2);

linkedList.add(6);

linkedList.add(0);

linkedList.add(3);

linkedList.add(8);

linkedList.add(10);

linkedList.removeFirst();

linkedList.removeFirst();

linkedList.removeLast();

System.out.println(linkedList.size());

System.out.println("遍历链表");

linkedList.traverseList();

linkedList.add(0,4);

linkedList.add(0,5);

linkedList.add(2,5);

linkedList.add(4,5);

linkedList.add(6,9);

linkedList.add(8,11);

linkedList.add(9,222);

// linkedList.linkBefore(3,new Node(3,null));

// linkedList.linkBefore(3,new Node(2,null));

// linkedList.linkBefore(3,new Node(2,null));

// linkedList.linkBefore(7,new Node(2,null));

// linkedList.linkBefore(9,new Node(7,null));

// linkedList.linkBefore(9,new Node(8,null));

System.out.println("遍历链表");

linkedList.traverseList();

linkedList.clearList();

}

}

以上就是Java简单实现线性表的链式存储，更多功能可参考Java集合中的LinkedList实现。

}

//插入位置是否越界

public Boolean isPositionIndex(int index){

return index>=0&&index<=size;

}

//检验下标是否越界，抛出异常

private void checkElementIndex(int index){

if(!isElementIndex(index)){

try {

throw new IndexOutOfBoundsException("下标越界");

} catch (Exception e) {

e.printStackTrace();

}

}

}

//检验插入下标是否越界，抛出异常

private void checkPositionIndex(int index){

if(!isPositionIndex(index)){

try {

throw new IndexOutOfBoundsException("下标越界");

} catch (Exception e) {

e.printStackTrace();

}

}

}

//返回指定位置的元素

private Node node(int index){

int nowIndex = 0;

if(size>0){

for (Node p=head;p!=null;){

if (nowIndex==index){

return p;

}

p=p.next;

nowIndex++;

}

}

return null;

}

public static void main(String[] args) {

java.util.LinkedList linkedList0=new java.util.LinkedList();

linkedList0.add(6);

linkedList0.remove(0);

linkedList0.size();

linkedList0.peek();

//linkedList0.getFirst();

linkedList0.clear();

//测试

LinkedList linkedList=new LinkedList();

linkedList.add(2);

linkedList.add(6);

linkedList.add(0);

linkedList.add(3);

linkedList.add(8);

linkedList.add(10);

System.out.println(linkedList.get(0));

System.out.println(linkedList.getFirst());

System.out.println(linkedList.getLast());

System.out.println(linkedList.get(5));

System.out.println(linkedList.remove(5));

System.out.println(linkedList.remove(4));

linkedList.remove(2);

linkedList.remove(0);

linkedList.remove(0);

linkedList.remove(0);

linkedList.add(2);

linkedList.add(6);

linkedList.add(0);

linkedList.add(3);

linkedList.add(8);

linkedList.add(10);

linkedList.removeFirst();

linkedList.removeFirst();

linkedList.removeLast();

System.out.println(linkedList.size());

System.out.println("遍历链表");

linkedList.traverseList();

linkedList.add(0,4);

linkedList.add(0,5);

linkedList.add(2,5);

linkedList.add(4,5);

linkedList.add(6,9);

linkedList.add(8,11);

linkedList.add(9,222);

// linkedList.linkBefore(3,new Node(3,null));

// linkedList.linkBefore(3,new Node(2,null));

// linkedList.linkBefore(3,new Node(2,null));

// linkedList.linkBefore(7,new Node(2,null));

// linkedList.linkBefore(9,new Node(7,null));

// linkedList.linkBefore(9,new Node(8,null));

System.out.println("遍历链表");

linkedList.traverseList();

linkedList.clearList();

}

}

以上就是Java简单实现线性表的链式存储，更多功能可参考Java集合中的LinkedList实现。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。