Java数据结构（链表篇）

13-04-11 来源：[db:作者]

收藏我要投稿

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，链表比较方便插入和删除操作。

连接点：

[java]
package ch04Link;

public class Link {

    // 数据域
    private long data;

    // 指针域
    private Link next;

    // 构造函数
    public Link(long data) {
        this.data = data;
    }

    public long getData() {
        return data;
    }

    public void setData(long data) {
        this.data = data;
    }

    public Link getNext() {
        return next;
    }

    public void setNext(Link next) {
        this.next = next;
    }



}

package ch04Link;

public class Link {

// 数据域
private long data;

// 指针域
private Link next;

// 构造函数
public Link(long data) {
this.data = data;
}

public long getData() {
return data;
}

public void setData(long data) {
this.data = data;
}

public Link getNext() {
return next;
}

public void setNext(Link next) {
this.next = next;
}

}

测试连接点：

[java]
package ch04Link;

public class TestLink {

    public static void main(String[] args) {
        Link link1 = new Link(10);
        Link link2 = new Link(50);
        Link link3 = new Link(20);
        Link link4 = new Link(100);

        link1.setNext(link2);
        link2.setNext(link3);
        link3.setNext(link4);

        System.out.println(link1.getData());
        System.out.println(link1.getNext().getData());
        System.out.println(link1.getNext().getNext().getData());
        System.out.println(link1.getNext().getNext().getNext().getData());
    }
}

package ch04Link;

public class TestLink {

public static void main(String[] args) {
  Link link1 = new Link(10);
  Link link2 = new Link(50);
  Link link3 = new Link(20);
  Link link4 = new Link(100);

  link1.setNext(link2);
  link2.setNext(link3);
  link3.setNext(link4);

  System.out.println(link1.getData());
  System.out.println(link1.getNext().getData());
  System.out.println(link1.getNext().getNext().getData());
  System.out.println(link1.getNext().getNext().getNext().getData());
}
}

链表：

[java]
package ch04Link;

/**
* 链表：核心思想：链表中只包含一个数据项，即对第一个连接点的引用
* @author hadoop
*
*/
public class LinkList {

    private Link first;

    // 插入
    public void insert(long value){
        Link link = new Link(value);
        if(first == null)
            first = link;
        else{
            link.setNext(first);
            first = link;
        }
    }

    // 打印链表
    public void display(){
        Link current = first;
        while(current != null){
            System.out.print(current.getData() + " ");
            current = current.getNext();
        }
    }

    // 查询链表
    public Link find(long key){
        Link current = first;
        while(current.getData() != key){
            if(current.getNext() == null)
                return null;
            current = current.getNext();
        }
        return current;
    }

    // 插入节点到指定位置
    public void insert(long value, int pos){
        if(pos == 0)
            insert(value);
        else{
            Link current = first;
            for(int i = 0; i < pos - 1; i++)
                current = current.getNext();
            Link link = new Link(value);
            link.setNext(current.getNext());
            current.setNext(link);
        }
    }

    // 删除节点
    public void delete(long value){
        Link current = first;
        Link ago = first;
        while(current.getData() != value){
            if(current.getNext() == null)
                return;
            else{
                ago = current;
                current = current.getNext();
            }
        }
        if(current == first)
            first = first.getNext();
        else
            ago.setNext(current.getNext());
    }
}

package ch04Link;

/**
* 链表：核心思想：链表中只包含一个数据项，即对第一个连接点的引用
* @author hadoop
*
*/
public class LinkList {

private Link first;

// 插入
public void insert(long value){
  Link link = new Link(value);
  if(first == null)
   first = link;
  else{
   link.setNext(first);
   first = link;
  }
}

// 打印链表
public void display(){
  Link current = first;
  while(current != null){
   System.out.print(current.getData() + " ");
   current = current.getNext();
  }
}

// 查询链表
public Link find(long key){
  Link current = first;
  while(current.getData() != key){
   if(current.getNext() == null)
    return null;
   current = current.getNext();
  }
  return current;
}

// 插入节点到指定位置
public void insert(long value, int pos){
  if(pos == 0)
   insert(value);
  else{
   Link current = first;
   for(int i = 0; i < pos - 1; i++)
    current = current.getNext();
   Link link = new Link(value);
   link.setNext(current.getNext());
   current.setNext(link);
  }
}

// 删除节点
public void delete(long value){
  Link current = first;
  Link ago = first;
  while(current.getData() != value){
   if(current.getNext() == null)
    return;
   else{
    ago = current;
    current = current.getNext();
   }
  }
  if(current == first)
   first = first.getNext();
  else
   ago.setNext(current.getNext());
}
}

测试：

[java]
package ch04Link;

public class TestLinkList {

    public static void main(String[] args) {
        LinkList linkList = new LinkList();

        linkList.insert(20);
        linkList.insert(80);
        linkList.insert(40);
        linkList.insert(60);
        linkList.display();
        System.out.println();

        System.out.println("找到节点，数据为：" + linkList.find(80).getData());

        linkList.insert(100, 0);
        linkList.display();

        System.out.println();

        linkList.delete(80);
        linkList.display();
    }
}

package ch04Link;

public class TestLinkList {

public static void main(String[] args) {
  LinkList linkList = new LinkList();

  linkList.insert(20);
  linkList.insert(80);
  linkList.insert(40);
  linkList.insert(60);
  linkList.display();
  System.out.println();

  System.out.println("找到节点，数据为：" + linkList.find(80).getData());

  linkList.insert(100, 0);
  linkList.display();

  System.out.println();

  linkList.delete(80);
  linkList.display();
}
}

比较链表和顺序表：

[java]
package ch04Link;

import ch01Array.MyArray;

public class Test {

    public static void main(String[] args) {
        // 构造链表
        long date1 = System.currentTimeMillis();
        LinkList linkList = new LinkList();
        for(int i = 0; i < 1000000; i++)
            linkList.insert(i);
        long date2 = System.currentTimeMillis();
        System.out.println(date2 - date1);

        // 构造顺序表
        long date3 = System.currentTimeMillis();
        MyArray myArray = new MyArray(1000000 + 1);
        for(int i = 0; i < 1000000; i++)
            myArray.insert(i);
        long date4 = System.currentTimeMillis();
        System.out.println(date4 - date3);

        // 链表删除
        long date5 = System.currentTimeMillis();
        linkList.delete(60000);
        long date6 = System.currentTimeMillis();
        System.out.println(date6 - date5);

        // 顺序表删除
        long date7 = System.currentTimeMillis();
        myArray.delete(60000);
        long date8 = System.currentTimeMillis();
        System.out.println(date8 - date7);
    }
}

点击复制链接与好友分享!回本站首页